Tóm tắt đề bài: Cho số nguyên dương ~n~, hãy in ra các ước ~x~ của ~n~ mà thỏa mãn ~x - 1~ hoặc ~x + 1~ cũng là ước của ~n~.

Subtask 1: ~n \le 10^6~

Duyệt ~i~ từ ~1~ đến ~n~ và kiểm tra xem ~i~, ~i - 1~, ~i + 1~ có phải ước của ~n~ hay không.

Độ phức tạp: ~O~ (~n~).

Subtask 2: ~n \le 10^{12}~

Ta duyệt đến ~\sqrt n~ để có một danh sách các ước của ~n~. Ta sắp xếp danh sách này lại.

Với mỗi phần tử của danh sách, ta chỉ cần xem phần tử ngay trước nó, và phần tử ngay sau nó có chênh lệch đúng một đơn vị hay không. Nếu có, đây là một phần tử thỏa mãn.

Độ phức tạp: ~O~ (~\sqrt n~).

Subtask 3: ~n \le 10^{18}~.

Ta cần một cách để lấy ra mọi ước của ~n \le 10^{18}~.

Bản chất, nếu ta có thể phân tích ~n~ ra thừa số nguyên tố: ~n = p_1^{d_1} \times p_2^{d_2} \times ... \times p_k^{d_k}~ thì ta có thể gọi đệ quy: với mỗi thừa số ta chọn ra một số mũ. Từ đó ta sinh ra được mọi ước của ~n~.

Vấn đề đặt ra là phân tích ~n~ ra thừa số nguyên tố. Ta có thể sử dụng thuật toán Pollard-Rho để làm điều này.

Một cách khác (credit: Phước Vũ) là: Một số nguyên dương ~n~ có ước đặc biệt là ~x~ sẽ có dạng ~x \times (x + 1) \times k~, với ~k~ cũng nguyên dương.

Bằng phản chứng, ta có thể chứng minh được ~min (x, k) \le 10^6~. Ta có thể duyệt ~x~, hoặc duyệt ~k~ để tính kết quả. Cần cẩn thận để tránh tính trùng.

Độ phức tạp ~O~ (~\sqrt {\sqrt n}~) hoặc ~O~ (~t \times 10^6~).