题目大意：求小于n的与n不互质的数的和。
题解：首先欧拉函数可以求出小于n的与n互质的数的个数，然后我们可以发现这样一个性质，当x与n互质时，n-x与n互质，那么所有小于n与n互质的数总是可以两两配对使其和为n，这也就是为什么当n大于2时欧拉函数都是偶数，知道这一点后，就可以计算出小于n与n互质的数的和了，那么不互质的和只要用总和来减就可以了。
#include <cstdio>
typedef long long LL;
LL n,ans;
LL Eular(LL n){
LL ret=1;
for(int i=2;i*i<=n;i++){
if(n%i==0){
n/=i,ret*=(i-1);
while(n%i==0)n/=i,ret*=i;
}
}
if(n>1)ret*=(n-1);
return ret;
}
int main(){
while(~scanf("%lld",&n)&&n){
ans=n*(n+1)/2-n;
ans-=Eular(n)*n/2;
printf("%lld\n",ans%1000000007);
}return 0;
}
原文：http://www.cnblogs.com/forever97/p/3940284.html