Nothing particularly crafty required - just find the Prime Factorisation of each number:
N=P_1^{k_1}P_2^{k_2}\dots P_m^{k_m}
where the P_i's are the primes less than or equal to 10^6. Then every divisor d of N will be of the form:
d=P_1^{l_1}P_2^{l_2}\dots P_l^{l_m}
where each l_i \le k_i. Compute all (k_1 + 1) \times (k_2 + 1) \times \dots \times (k_m + 1) such d and find the xor of all of them.
Here’s my solution.
Not sure why it’s 10x slower than everyone elses XD
What will be the complexity of this solution?
Roughly O(T \times (\textit{num primes up to }10^6 + \textit{max num divisors of number }\le 10^{18}))
Thanks! I understood that already.
I was looking for more like this : Upper bound for number of divisors - Codeforces
So it is roughly : O ( T * 10**6 )