EXPGCD - Editorial

editorial
, , , , , ,
2

I little more math and we can get, i+sum[i] = phi[i]

Here we assume mu[1]=0,

instead we take the original mobius function, we can reduce i+sum[i] of previous case into sum[i].

Now we can use Dirichlet convolution and obtain sum[i] = idOmu;

Now we know phiOI = id and muOI = en;

therefore idOmu = phiOIOmu = phiOen = phi(n);

Here is my accepted solution.

Refernce : https://www.quora.com/profile/Surya-Kiran/Posts/A-Dance-with-Mobius-Function?fbclid=IwAR1fRllkPF6w4CqkYS9YKwgMOgcYwgOF9DYzFTMzcd5_EHg6-jCY3fgtJQQ

I learned about Mobius function in this challenge, so there might be a chance of errors.

2 Likes