for above problem why normal approach in which we consider the xor of all divisors ,it shows time limit error if possible please provide complete solution and what should be right approach , i saw most of correct submission but unable to get it how they has less time complexity
1 Like
Can u explain why we calculate l1*l2…lm.
Any proof of it.
Actually, I got that slightly wrong - fixed now 
How many ways are there of choosing l_1 subject to 0 \le l_1 \le k_1? How many ways are there of choosing the pair (l_1, l_2) subject to 0 \le l_1 \le k_1 and 0 \le l_2 \le k_2? Etc.
1 Like
I understand that we first find all prime and it’s power say k1 k2 …km. then knowing this how we find the answer…
Say I have pi and it’s power ki so we loop all the powers of pi.
Ex pi=2 and ki=3 so for the pi=2,we have 2xor4xor8… and similarly for all pi.
Pls correct me if I’m wrong
Let’s use a specific example - say N=24. Then N=p_1^3 p_2^1 where the primes p_1=2 and p_2=3, and k_1=3 and k_2=1. To find all divisors of N, we need to compute:
p_1^0 p_2^0=1
p_1^0 p_2^1=3
p_1^1 p_2^0=2
p_1^1 p_2^1=6
p_1^2 p_2^0=4
p_1^2 p_2^1=12
p_1^3 p_2^0=8
p_1^3 p_2^1=24
i.e. all (k_1 + 1) \times (k_2 + 1) possible divisors.
2 Likes
Amazing, thanks a lot man…
U save a day…
1 Like