Tóm tắt đề bài

Cho 2 số nguyên dương ~a~ và ~b~ (~a, b \le 10^{12}~) lần lượt là số kẹo chanh và dừa. Hỏi có bao nhiêu cách chia sao cho số lượng kẹo mỗi loại các bạn nhận được là bằng nhau.

Subtask 1: ~A, B \le 10^7~

Ta có thể viết lại bài toán như sau: Tìm tất cả các ước số chung của ~A~ và ~B~.

Ta có thể duyệt ~i~ từ ~1~ đến ~max(A, B)~ để kiểm tra xem liệu ~i~ có phải là ước chung của ~A~ và ~B~ hay không.

ĐPT: ~O~(~max(A, B)~)

Subtask 2: ~A, B \le 10^{12}~

Theo phản chứng, ta có thể chứng minh như sau:

Nếu ~a \times b = x~, thì ít nhất một trong hai số ~a~ hoặc ~b~ sẽ ~\le \sqrt{x}~. Do đó, ta chỉ cần xét tới ~\sqrt{max(A, B)}~ rồi làm tương tự như subtask 1.

ĐPT: ~O~(~\sqrt{max(A, B)}~)

Subtask 3: Không có giới hạn gì thêm

Do giới hạn rất lớn, ta hoàn toàn không thể duyệt theo phương pháp thông thường (trial division).

Nhận xét: Với ~n \le 10^{17}~, chỉ có khoảng ~10^6~ ước số. Ta có thể sử dụng các thuật toán sau để có thể phân tích thừa số với giới hạn trên:

• Pollard's Rho.
• Miller-Rabin.

Từ các thừa số ta thu được, ta có thể sinh tập ước bằng đệ quy.

ĐPT: ~O~(~gcd(A, B)^{1/4}~)

Bonus

Subtask 3 là một subtask tương đối khó để cài thuật chuẩn hoàn toàn trong phòng thi, nên mình sẽ giới thiệu một cách khác có thể qua được tương đối số điểm và cài đặt cũng dễ thở hơn.

Đây là một phương pháp tối ưu từ tư tưởng trial division.

Ý tưởng cơ bản của thuật toán này như sau:

Nhận xét: Số nguyên tố ~> 3~ sẽ luôn có dạng ~6k + 1~ hoặc ~6k - 1~ (bạn đọc tự chứng minh).

Do đó, ta có thể cài như sau:

• Xử lý riêng các thừa số nhỏ (như ~2~ và ~3~).
• Từ ~5~ trở đi, ta có thể kiểm tra xem liệu đó có phải là thừa số nguyên tố hay không với bước nhảy ~i~ là ~6~.

ĐPT: ~O~(~\frac{\sqrt{n}}{6}~)

Lưu ý rằng, trong một số trường hợp, phương pháp này vẫn sẽ không vượt qua tất cả các test với thời gian chạy là 1s.