【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2705
【题目大意】
求出∑gcd(i,N)(1<=i<=N)
【题解】
$∑_{i=1}^{N}gcd(i,N)$
$=∑_{i=1}^{N}∑_{d|gcd(i,N)}\phi(d)$
$=∑ \phi(d)∑ _{1=<i<=N \land d|i \land d|N}1$
$=∑_{d|N}\phi(d)\lfloor\frac{i}{d}\rfloor$
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
int Euler(int n){
int t=1,i;
if(!(n&1))for(n>>=1;!(n&1);n>>=1,t<<=1);
for(i=3;i*i<=n;i+=2)if(n%i==0)for(n/=i,t*=i-1;n%i==0;n/=i,t*=i);
if(n>1)t*=n-1;
return t;
}
int main(){
int n;
long long ans=0;
while(~scanf("%d",&n)){
for(int i=1;i*i<=n;i++){
if(n%i==0){
ans+=1LL*i*Euler(n/i);
if(i*i<n)ans+=1LL*(n/i)*Euler(i);
}
}printf("%lld\n",ans);
}return 0;
}
BZOJ 2705 [SDOI2012]Longge的问题（欧拉函数）
原文：http://www.cnblogs.com/forever97/p/bzoj2705.html