Hướng dẫn giải của [TS10 Quảng Trị 2025 - 2026] Chia kẹo
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nếu chia được cho ~n~ bạn thì ~n~ phải đồng thời là ước của ~A~ và ~B~. Do đó ~n~ chính là một ước dương của ~g=\gcd(A,B)~.
Ta cần sinh toàn bộ ước dương của ~g~, sắp xếp tăng dần, rồi với mỗi ước ~n~ in ~n, A/n, B/n~.
Với giới hạn lớn, có thể phân tích ~g~ bằng Miller-Rabin kết hợp Pollard Rho, sau đó sinh các ước từ phân tích thừa số nguyên tố.
Bình luận