BZOJ2705 - Click Here
Description
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
Input
一个整数，为N。
Output
一个整数，为所求的答案。
Solutions
$N$是固定的，因此$(i,N)$只可能是$N$的约数，而$N$的约数最多只有$2\sqrt N$个。
考虑枚举约数，则答案变成$\sum_{k \mid N} k\sum_{1 \leq i \leq N} [(i,N)=k]$
对内层和式变形可得，$\sum_{k \mid N} k\sum_{1 \leq i \leq N}[(\frac{i}{k},\frac{N}{k})=1]$
内层和式$\sum_{1 \leq i \leq N}[(\frac{i}{k},\frac{N}{k})=1]$实质上就是$\phi(\frac{N}{k})$
因此最后答案为$\sum_{k \mid N}k \cdot \phi(\frac{N}{k})$
暴力求欧拉函数即可。
时间复杂度$O(N)$。不过这个上界很宽松，实际在OJ上是能跑过的qwq。
CODE
CODE - Click Here