//求小于n且和n不互质的所有数之和
//若gcd(n , i) == 1 那么 gcd(n , n-i) == 1
//可以用反证法
//设gcd(n , n-i) != 1;
//那么可以有 n = k1*a
//n - i = k2*a ;
//i = (k1-k2)*a
//gcd(n ,i) != 1
//那么 ans = n*(n-1)/2 - n*euler(n)/2
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
typedef __int64 ll ;
const int mod = 1000000007 ;
ll Euler(ll n)
{
ll res = n ;
for(ll i = 2;i*i <= n;i++)
{
if(n%i == 0)
res -= res/i ;
while(n%i == 0)
n/=i ;
}
if(n > 1)res -= res/n ;
return res ;
}
int main()
{
ll n ;
while(scanf("%I64d" , &n) && n)
{
ll sum = Euler(n) ;
//cout<<sum<<endl;
ll ans = (((n)*(n-1)/2) - n*sum/2)%mod ;
printf("%I64d\n" , ans) ;
}
return 0 ;
}
hdu3501 Calculation 2 欧拉函数
原文：http://blog.csdn.net/cq_pf/article/details/46136037
