CodeChef Simple Sum

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

 

틀린 부분이 있을 것 같기도 하지만 일단 내가 이해한대로 적어본다.

$$\sum ^n _{i=1}\frac{n}{\gcd (i,n)}=\sum_{k|n}\sum ^n _{i=1}[\gcd(i,n)=k]\frac{n}{k}$$

\(i=ak\)라고 하면,
$$\sum_{k|n}\sum ^{\frac{n}{k}} _{a=1}[\gcd(a,\frac{n}{k})=1]\frac{n}{k}=\sum_{k|n}\sum ^{\frac{n}{k}} _{a=1}\sum _{d|\gcd(a, \frac{n}{k})} \mu(d) \frac{n}{k}=\sum_{k|n}\sum ^{\frac{n}{k}} _{a=1}\sum ^{\frac{n}{k}} _{d=1} [d|a][d|\frac{n}{k}]\mu(d)\frac{n}{k}$$

$$=\sum_{k|n}\frac{n}{k}\sum^{\frac{n}{k}}_{d=1}[d|\frac{n}{k}]\mu(d)\sum^{\frac{n}{k}}_{a=1}[d|a]=\sum_{k|n}\frac{n}{k}\sum^{\frac{n}{k}}_{d=1}[d|\frac{n}{k}]\mu(d)\frac{n}{kd}=\sum_{k|n}\frac{n}{k}\sum_{d|\frac{n}{k}}\mu(d)\frac{n}{kd}=\sum_{k|n}\frac{n}{k}\phi(\frac{n}{k})=\sum_{k|n}k\phi(k)$$

가 되므로 문제에서 구해야 하는 것은 \(n\)의 모든 약수 \(k\)에 대해서 \(k\phi(k)\)의 합과 같다.

\(n\)이 어떤 소인수 \(p\)가 있어서 \(n=p^em\)이면(\(m\)은 \(p\)의 배수가 아니여야 한다. = \(e\)는 최대한 커야한다.), 

$$\sum_{k|n}k\phi(k)=\sum^e _{\alpha=0}\sum_{k|m}kp^\alpha \phi(kp^\alpha)=\sum^e_{\alpha=0}\sum_{k|m}k\phi(k)p^\alpha\phi(p^\alpha)=\left(\sum^e_{\alpha=0}p^\alpha\phi(p^\alpha)\right)\left(\sum_{k|m}k\phi(k)\right)$$

이므로 같은 방식으로 \(n\)을 소인수분해해서 각 소인수별로 \(\sum^e_{\alpha=0}p^\alpha\phi(p^\alpha)\)을 구한 뒤 곱해주면 된다.

 

중간에 \(\frac{n}{k}\)들을 다 \(k\)로 바꿔야 보기 좋을 것 같다...