How to solve gcdex2 from SPOJ?

Revision en1, by PanicStation, 2017-12-16 01:22:10

How to solve this problem from [http://www.spoj.com/problems/GCDEX2/] ? I have already solved this problem [http://www.spoj.com/problems/GCDEX/] with help of this blog [https://www.quora.com/profile/Surya-Kiran/Posts/A-Dance-with-Mobius-Function]. but I don't think i can use the same technique on the above problem because the N is too big.

Tags mobius inversion formula, gcd, eular phi

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English PanicStation 2017-12-16 01:25:24 81
en1 English PanicStation 2017-12-16 01:22:10 378 Initial revision (published)