题目链接：bzoj2705 题目大意： 求 ∑ni=1gcd(i,n) ， 0<N≤232 。
题解： 数论，欧拉函数 设 d 为n的约数，有 i=i′×d 于是式子就可以写成
∑d|nd∑1≤i′d≤n,(i′d,n)=d1 即 ∑d|nd∑1≤i′≤nd,(i′,nd)=11 继而化为： ∑d|nd×ϕ(nd) 于是就 O(n√) 枚举 d ，直接计算ϕ(nd)，累加就好了。 额，先 O(n√) 预处理出 n 的所有质因子吧，因为nd的质因子一定也在 n <script type="math/tex" id="MathJax-Element-60">n</script>的质因子中。 #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; LL cnt,pri[50]; void get_pri(LL x,LL lim) { cnt=0; for (LL i=2;x!=1 && i<=lim;i++) if (x%i==0) { pri[++cnt]=i; while (x%i==0) x/=i; } if (x!=1) pri[++cnt]=x; } LL phi(LL x) { LL ret=x; for (LL i=1;i<=cnt;i++) if (x%pri[i]==0) ret=ret*(pri[i]-1)/pri[i]; return ret; } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); LL i,n,ans=0; scanf("%lld",&n); LL m=(LL)sqrt(n); get_pri(n,m); for (i=1;i<=m;i++) if (n%i==0) { LL x=i,y=n/i; ans+=x*phi(y); ans+=y*phi(x); } if (m*m==n) ans-=m*phi(m); printf("%lld\n",ans); return 0; }