HDU 3501 Calculation 2(欧拉函数的应用)

 1 #include <stdio.h>
 2 #define LL __int64
 3 
 4 int eular(int n){
 5     int ret = 1;
 6     for(int i = 2; i*i <= n;i++)
 7         if(n%i == 0){
 8             n /= i, ret *= i-1;
 9             while(n%i == 0)
10                 n /= i, ret *= i;
11         }
12     if(n > 1)
13         ret *= n-1;
14     return ret;
15 }
16 
17 LL n, m;
18 
19 int main()
20 {
21     while(~scanf("%I64d", &n) && n)
22     {
23         LL sum = n*(n+1)/2-n; ///计算所有数总数
24         LL t = eular(n)*n/2; ///计算互质的数总和
25         sum -= t;
26         sum %= 1000000007;
27         printf("%I64d\n", sum);
28     }
29 
30     return 0;
31 }