Calculation 2
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1750 Accepted Submission(s): 727
Problem Description
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.
Input
For 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.
Output
For each test case, you should print the sum module 1000000007 in a line.
Sample Input
3
4
0
Sample Output
0
2
1 /* 2 欧拉函数一个小小的性质： 3 4 求小于n并且与n互质的数的和为：n*phi[n]/2； 5 6 这个好像以前有点印象的。 7 8 */ 9 10 #include11 12 13 __int64 Euler(__int64 n)14 {15 __int64 temp=n,i;16 for(i=2;i*i<=n;i++)17 {18 if(n%i==0)19 {20 while(n%i==0)21 n=n/i;22 temp=temp/i*(i-1);23 }24 }25 if(n!=1) temp=temp/n*(n-1);26 return temp;27 }28 29 int main()30 {31 __int64 n,m;32 __int64 k;33 while(scanf("%I64d",&n)>0)34 {35 if(n==0)break;36 m=Euler(n);37 k=m*n/2;38 k=n*(n+1)/2-n-k;39 //刚开始，只有k为__in64，错了。40 //这里相乘之后，可能会超过int范围。倒置溢出41 k=k%1000000007;42 printf("%I64d\n",k);43 }44 return 0;45 }