要我们求小于n并且不与n互素的数字的和， 那么可以转化为1->(n-1)的和减去小于n且与n互素的数字的和
首先，有gcd(n,i)=1, 那么gcd(n,n-i)=1, 这是因为如果a%s=0, b%s=0, 那么(a-b)%s=0
所以gcd(n,i)=1, 那么gcd(n,n-i)=1, 如果gcd(n,n-i)!=1 ,那么 gcd(n,n-(n-i))!=1,所以 如果gcd(n,i)=1,那么gcd(n,n-i)=1成立
下面设小于n且与n素数的数字的和为sum
sum = a[0] + a[1] + a[2] + ... + a[phi[n]], (a[i]表示与n互素的数字）
sum = (n-a[0]) + (n-a[1]) + (n-a[2])+...+(n-a[phi[n]])
两个式子相加， 2*sum = phi[n]*n->sum = phi[n]*n/2
1->(n-1)的和为n*(n-1)/2
所以最终答案为n*(n-1)/2 - phi[n]*n/2
数据太大，要用long long
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
/* */ int euler(int n)
{
int m = sqrt(n) + 0.5;
int ans = n;
for (int i = ; i <= m; ++i)
if (n%i == )
{
ans = ans / i * (i - );
while (n%i == ) n /= i;
}
if (n > ) ans = ans / n *(n - );
return ans;
}
int main()
{ LL n;
while (scanf("%I64d", &n), n)
{
LL t = euler(n)*n/;
LL ans = n*(n - ) / - t;
printf("%I64d\n", ans % );
}
return ;
}