Calculation 2

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1923    Accepted Submission(s): 812

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

 

 

Author

GTmac

 

 

Source

 

 

Recommend

zhouzeyong   |   We have carefully selected several similar problems for you:            

 

1 //15MS    208K    517 B    G++ 2 /* 3  4         一开始用的是求其模数加上模数倍数，后来发现会出现重复加， 5     即要用到容斥原理，不过没试过就放弃了。 6         后来查了发现 n*euler(n)/2 即n及n的欧拉数积除以二的结果为 7     小于n且与n互质的数的和，然后解决。  8  9 */10 #include
     
      11 #define N 100000000712 int euler(int n) //直接求法 13 {14     int ret=1;15     for(int i=2;i*i<=n;i++){16         if(n%i==0){17             n/=i,ret*=i-1;18             while(n%i==0){19                 n/=i,ret*=i;20             }21         }22     }23     if(n>1) ret*=n-1;24     return ret;25 } 26 __int64 cul(__int64 n)27 {28     return (n*(n+1)/2-n*euler((int)n)/2-n)%N;29 }30 int main(void)31 {32     __int64 n;33     while(scanf("%I64d",&n),n)34     {35         printf("%I64d\n",cul(n));36     }37     return 0; 38 }