Mình xin chia sẻ lời giải bài này như sau:

Đầu tiên bài toán ta sẽ định nghĩa lại số "tương lai" theo một cách khác như sau: Số tương lai là số có dạng: \(p * q\) trong đó \(p,q\) là các số nguyên tố.

Do đó một số nguyên dương \(N\) được gọi là số "tương lai" nếu nó có dạng: \(N=p * q\), trong đó \(p,q\) là các số nguyên tố và chúng không nhất thiết phân biệt.

Gọi \(v(N)\) là số lượng ước của \(N\), thì để \(N\) là số "tương lai", \(v(N)\) phải thoả mãn các điều kiện sau:

• \(v(N)=4\) với \(N\) không phải là số lập phương

• \(v(N)=3\) tức \(N\) là bình phương của một số nguyên tố.

Ở đây, để giúp các bạn hiểu rõ hơn về \(v(N)\) mình xin bổ sung thêm một số kiến thức liên quan đến \(v(N)\) như sau:

Xét một số nguyên dương \(X\) bất kì, và \(X\) được phân tích thành thừa số nguyên tố với dạng: \(X = p_1^{\alpha_1}p_2^{\alpha_2}...p_r^{\alpha_r}\) (với \(p_i\) là các số nguyên tố và \(\alpha_i\) là các số nguyên dương, \(i=\overline{1,r},r\in \mathbb{N}^*\))

Khi đó \(v(X)=(\alpha_1+1)(\alpha_2+1)...(\alpha_r+1)\)

Ví dụ:

• Với \(X=16\), ta có: \(X=2^4\implies v(X) = 4+1 = 5\). Vậy số \(16\) có tổng cộng \(5\) ước. (Nếu liệt kê thì nó sẽ gồm {\(1,2,4,8,16\)})

• Với \(X=6\), ta có: \(X=2*3\implies v(X) = (1+1)(1+1) = 4\). Vậy số \(6\) có tổng cộng \(4\) ước. (Nếu liệt kê thì nó sẽ gồm {\(1,2,3,6\)}).

Do đó, quay trở lại bài toán gốc, công việc của ta chỉ là đi xác định số lượng ước của \(N\) và thoả mãn các điều kiện:

• \(v(N)=4\) với \(N\) không phải là số lập phương (vì nếu nếu \(N\) là lập phương thì nó sẽ tồn tại 1 ước không phải là số nguyên tố. Ví dụ \(N=8=2^3\). Khi đó nó sẽ có số \(4\) là ước không phải là số nguyên tố)

• \(v(N)=3\) tức \(N\) là bình phương của một số nguyên tố.

Tiếp theo, ta sẽ đi tìm thuật toán để giải quyết vấn đề tìm số lượng của của một số nguyên dương \(N\).

Thì để tiết kiệm thời gian, mình xin chia sẻ các bạn một thuật toán với độ phức tạp \(O(\sqrt[3]{N})\) đã được viết tại đây

Và mình xin tóm tắt pseudo-code:

N = input()
primes = array containing primes till 10^6
ans = 1
for all p in primes :
            if p*p*p > N:
                  break
            count = 1
            while N divisible by p:
                  N = N/p
                  count = count + 1
            ans = ans * count
if N is prime:
            ans = ans * 2
else if N is square of a prime:
            ans = ans * 3
else if N != 1:
            ans = ans * 4

Đến đây, công việc còn lại chúng ta chỉ là viết các câu lệnh if-else đơn giản để giải quyết nốt bài toán.

Ngoài ra, trong quá trình tìm số lượng ước này, chúng ta cần phải dùng thêm sàng nguyên tố để xác định được tập số các số nguyên tố, và kiểm tra xem một số có phải là số

nguyên tố hay không !

Đến đây, bài toán đã được giải quyết hoàn tất.

Xét về độ phức tạp của tổng quan bài toán một chút, thì nó sẽ là: \(O(10^6*\sqrt[3]{2.10^{7}})\sim O(2.10^{8})\) - Hoàn toàn có thể giải quyết được trong Time limit của bài toán !

Ps1: Trick khó nhất của bài này nằm ở chỗ: \(v(N)=4\) và phải thêm điều kiện \(N\) không phải là số lập phương!

Ps2: Nếu đã cố gắng hết sức mà vẫn chưa ra, các bạn có thể tham khảo code tại đây

Updated: Sau khi bị các author làm chặt time lại, nên mình đã optimize code một chút, giảm độ phức tạp từ \(O(2 * 10^8)\) về còn \(O(10^7)\)

Cụ thể như sau, ý tưởng ta sẽ sàng 2 lần:

• Lần 1: Sàng để đánh dấu tất cả các số là số nguyên tố từ \(1\) đến \(2 * 10^7\)

• Lần 2: Sàng để đanh dấu tất cả các số là tích của \(2\) số nguyên tố , và các số này cũng từ \(1\) đến \(2 * 10^7\)

Thuật toán lần 1 và lần 2 tương tự nhau, ở lần 2 được tạo nên từ lần 1, cụ thể như sau:

• Ứng với mỗi số là số nguyên tố \(k\), ta duyệt qua tất cả các bội của \(k\), và ta chỉ cần kiểm tra xem, các bội này khi chia cho \(k\) có tạo thành số nguyên tố hay không là được !

Ý tưởng chỉ có vậy thôi, các bạn có thể tham khảo code tại đây

Ps: Để tránh TLE, các bạn khai báo các mảng với kiểu dữ liệu là int thôi nhé, vì nếu dùng long long nó sẽ bị TLE