https://www.codechef.com/NOV15/problems/SMPLSUM

#1

https://www.codechef.com/NOV15/problems/SMPLSUM
how to solve this question and i read the editorial but i am not getting anything how they proved the formula…help me plz

#3

Here for a Number N:

  1. Compute all divisors
  2. For all divisors d : compute N/gcd(N,d) and multiply it with totient (N/gcd(N,d)) and sum them up will result the answer.
    Reason : For all diviors gcd(N,d) will be different . Let say
    N=15
    diviors : 1 , 3 , 5 ,15
    So, gcd(N,i) can be wither 1,3,5,15 and next you have to find how many numbers will result this gcd(N,i) . It can be easily seen by totient function
    https://discuss.codechef.com/questions/76893/smplsum-editorial