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$로 바꿔야 보기 좋을 것 같다...