hdu 3501（欧拉函数引申）-白红宇

hdu 3501（欧拉函数引申）

阅读量：6813 次

发布时间：2019-06-26

本文共 899 字，大约阅读时间需要 2 分钟。

题意：求小于N与N不互质的数的和

欧拉公式的引伸：小于或等于n的数中，与n互质的数的总和为：φ(x) * x / 2。(n>1)

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 using namespace std;13 14 typedef long long ll;15 typedef unsigned long long ull;16 const int mod = 1000000007;17 ll Eular(ll n)18 {19 ll res = n;20 if (n == 1)21 return 1;22 for (int i = 2; i*i <= n; i++)23 {24 if (n%i == 0)25 {26 res = res / i * (i - 1);27 while (n%i == 0)28 n = n / i;29 }30 }31 if (n != 1)32 {33 res = res / n * (n - 1);34 }35 return res;36 }37 int main()38 {39 ll n;40 while (cin >> n&&n)41 {42 43 ll ans = ((n - 1)*n / 2%mod - Eular(n)*n / 2 % mod +mod) %mod;44 cout << ans << endl;45 }46 return 0;47 }