Chef and Divisors : Div1 Please explain approach for this problem

https://www.codechef.com/ACD2019/problems/DIV1

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

2 Likes

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 : https://codeforces.com/blog/entry/14463
So it is roughly : O ( T * 10**6 )