description
求(sum_{i=1}^{n} gcd(i,n))
设(f(k)=sum_{gcd(i,n)==k} 1),则有(sum_{i=1}^{n}gcd(i,n)=sum_{d|n}dcdot f(d)),现欲求函数(f(k)).
可以发现,(f(k)=sum_{i=1}^{n}[gcd(i,n)==k]=sum_{i=1}^{lfloor frac{n}{k} floor}[gcd(i,lfloor frac{n}{k} floor)==1]=phi(lfloor frac{n}{k} floor))
故:原式(=sum_{d|n}dcdot phi(lfloor frac{n}{d} floor))