hdu 3501 Calculation 2 (欧拉函数)

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

Sample Output

Author

GTmac

Source

2010 ACM-ICPC Multi-University Training Contest（7）——Host by HIT

Recommend

zhouzeyong | We have carefully selected several similar problems for you: 3507 3506 3505 3504 3498

 1 //15MS    208K    517 B    G++
 2 /*
 3 
 4         一开始用的是求其模数加上模数倍数，后来发现会出现重复加，
 5     即要用到容斥原理，不过没试过就放弃了。
 6         后来查了发现 n*euler(n)/2 即n及n的欧拉数积除以二的结果为
 7     小于n且与n互质的数的和，然后解决。 
 8 
 9 */
10 #include<stdio.h>
11 #define N 1000000007
12 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
",cul(n));
36     }
37     return 0; 
38 }