求(sum_{i=1}^ngcd(i,n)),(n< 2^{31})。
解
理解1：
注意式子的实际意义，显然答案只可能在n的约数中，而现在问题变成了每个约数出现了几次,而一个约数d要出现的次数，自然需要这个数有约数d，其他的约数与之互斥，于是考虑欧拉函数，故我们有
[ans=sum_{d|n}varphi(n/d)d
]
以此枚举n的约数爆算即可，时间复杂度不难得知为(O(sigma(n)sqrt{n}))。
理解2：
约数计数问题，考虑反演，于是有
[ans=sum_{d=1}^ndsum_{i=1}^n(gcd(i,n)==d)
]
设
[f(d)=sum_{i=1}^n(gcd(i,n)==d)
]
[F(d)=[n/d](d|n)
]
由Mobius反演定理，带入原式我们有
[ans==sum_{d=1}dsum_{d|x,x|n}[n/x]mu(x/d)=
]
[sum_{x|n}[n/x]sum_{d|x}dmu(x/d)=sum_{x|n}[n/x]varphi(x)
]
同理解1做法即可。
于是我们可以小结一下，同排列组合一样，约数计数问题，也有它的实际意义的理解，两者侧重点不同，一个侧重思维，一个侧重代数变换，但是殊途同归，而且不难得知最后的答案其实就是(varphi *id)，我们可以使用杜教筛对之优化，数据范围可以出到(10^{11})，但无论如何，重点都在于对于约数的巧妙的理解。
参考代码：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define ll long long
using namespace std;
il ll Phi(ll);
int main(){
ll ans,n,i;
while(scanf("%lld",&n)!=EOF){
for(ans&=0,i=1;i*i<n;++i)
if(!(n%i)){
ans+=(n/i)*Phi(i);
ans+=(i)*Phi(n/i);
}
if(i*i==n)ans+=i*Phi(i);
printf("%lld
",ans);
}
return 0;
}
il ll Phi(ll n){
ri ll i,ans(n);
for(i=2;i<=n/i;++i)
if(!(n%i)){
(ans/=i)*=(i-1);
while(!(n%i))n/=i;
}if(n>1)(ans/=n)*=(n-1);
return ans;
}