求\(\sum_{i=1}^n(i,n),n\leqslant 10^9\)
\(\sum_{i=1}^n(i,n)=\sum_{d\mid n}d\sum_{i=1}^n[(i,n)=d]=\sum_{d\mid n}\sum_{i=1}^{\frac{n}{d}}[(i,\frac{n}{d})=1]=\sum_{d\mid n}\varphi(\frac{n}{d})\)
复杂度好像和杜教筛挺像的?口胡+1...我不太会算...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll phi(ll x) {
ll r=x;
for(int i=2;i*i<=x && x>1;i++) if(x%i==0) {
r=r/i*(i-1),x/=i;
for(;x%i==0;x/=i);
}if(x>1) r=r/x*(x-1);return r;
}
ll S(ll n) { return n*(n+1)/2; }
ll S(ll l,ll r) { return S(r)-S(l-1); }
ll F(ll n) {
ll r=0;
for(int i=1;i*i<=n;i++) if(n%i==0) {
r=r+i*phi(n/i);
if(i*i==n) continue;
r=r+n/i*phi(i);
}return r;
}
int main() {
ll n;
scanf("%lld",&n);
printf("%lld\n",F(n));
return 0;
}
原文：http://www.cnblogs.com/beiyuoi/p/6755024.html