hdu 3501 Calculation 2 (欧拉函数)

时间：2022-03-06 21:07:19

题目

题意：求小于n并且 和n不互质的数的总和。

思路：求小于n并且与n互质的数的和为：n*phi[n]/2 .

若a和n互质，n-a必定也和n互质(a<n)。也就是说num必定为偶数。其中互质的数成对存在。其和为n。

公式证明：

反证法：
如果存在K!=1使gcd(n,n-i)=k,那么(n-i)%k==0
而n%k=0
那么必须保证i%k=0
k是n的因子,如果i%k=0那么gcd(n,i)=k,矛盾出现;

所以先求出1……n-1 的和， 再用这个和 减去 上面公式求出来的值。

欧拉函数phi(m)：当m>1是，phi(m)表示比m小且与m互质的正整数个数

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 #define LL long long

 const int mo = ;

 LL phi(LL n)   //欧拉函数模板

 {

     LL i, m = (int)sqrt(n+0.5), ans = n;

     for(i = ; i <= m; i++)

     {

         if(n%i == )

             ans = ans/i*(i-);

         while(n%i == )

             n /= i;

     }

     if(n > ) ans = ans/n*(n-);

     return ans;

 }

 int main()

 {

     LL res, n, i;

     while(~scanf("%lld", &n) && n)

     {

         res = n*(n-)/;

         res -= phi(n)*n/;  //当n等于2的时候，phi为1，所以不能写成 phi(n)/2*n;

         printf("%lld\n", res%mo);

     }

     return ;

 }

再贴一个关于欧拉函数的讲解博客

相关文章