recently i encountered with this problem on spoj spoj_link i was trying to solve this problem using Pillai's arithmetical function for gcd sum in which Euler's totient function will be going to be implemented as we know that we can calculate gcd using following code where phi is Euler Totient function (pre-calculated).
1.void gcd() 2.{ 3. tot(); 4. for(int i=1;i<mm;i++) 5. { 6. for(int j=2;i*j<mm;j++) 7. { 8. res[i*j]+=i*phi[j]; 9. } 10. } 11. 12. for(int i=2;i<mm;i++) 13. { 14. res[i]+=res[i-1]; 15. } 16. }
- i was thinking of this lamma gcd(fib(a),fib(b))=fib(gcd(a,b)) but problem will be to make the pairs because n is very high.
- i was trying to modify the line number 8 res[i*j] to res[fib(pow(A[i],k)*fib(pow(A[j],k)] after the considering the effect of modulo 1e+9 as it will overflow the index of array so it's wrong approach basically i don't know how to solve it . please someone help.
