Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime ...
Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime to B if A, B share no common positive divisors except 1.
InputFor each test case, there is a line containing a positive integer N(1 ≤ N ≤ 1000000000). A line containing a single 0 follows the last test case.OutputFor each test case, you should print the sum module 1000000007 in a line.Sample Input
3 4 0
Sample Output
0 2
如果gcd(n,i)==1,gcd(n,n-i)==1
證：i=1(mod n)
-i=-1(mod n)
n-i=-1+n (mod n)
n-i=1 (mod n)
通過歐拉函數一個數n中存在phi(n)個與之互質的數，因為i+（n-i）為n也就是有n對。
則與n互質數目之和為res=phi(n)/2*n,
ans=(n-1)*n/2-res。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define N 1000010
#define maxn 1000010
#define mod 1000000007
using namespace std;
typedef long long ll;
int p[N];
int prime[N];
int pn=0;
bool vis[N];
int main()
{
for (int i = 2; i < N; i++) {
if (vis[i]) continue;
prime[pn++] = i;
for (int j = i; j < N; j += i)
vis[j] = 1;
}
ll n;
while(~scanf("%lld",&n),n)
{
ll r=n;
ll phi=n;
for(int i=0;prime[i]*prime[i]<=r;i++)
{
ll tem=0;
while(r%prime[i]==0)
{
r/=prime[i];
tem++;
}
if(tem)
phi=phi-phi/prime[i];
}
if(r!=1)
phi-=phi/r;
ll rem=n*phi/2;
ll ans=n*(n-1)/2;
printf("%lld\n",(ans-rem)%mod);
}
}
