首页 > 其他 > 详细

hdu 3501 Calculation 2 (欧拉函数)

时间:2014-05-05 09:50:13      阅读:593      评论:0      收藏:0      [点我收藏+]

题目

题意:求小于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互质的正整数个数

bubuko.com,布布扣
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <algorithm>
 7 using namespace std;
 8 #define LL long long
 9 const int mo = 1000000007;
10 
11 LL phi(LL n)   //欧拉函数模板
12 {
13     LL i, m = (int)sqrt(n+0.5), ans = n;
14     for(i = 2; i <= m; i++)
15     {
16         if(n%i == 0)
17             ans = ans/i*(i-1);
18         while(n%i == 0)
19             n /= i;
20     }
21     if(n > 1) ans = ans/n*(n-1);
22     return ans;
23 }
24 int main()
25 {
26     LL res, n, i;
27     while(~scanf("%lld", &n) && n)
28     {
29         res = n*(n-1)/2;
30         res -= phi(n)*n/2;  //当n等于2的时候,phi为1,所以不能写成 phi(n)/2*n;
31         printf("%lld\n", res%mo);
32     }
33     return 0;
34 }
bubuko.com,布布扣

 

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

 

hdu 3501 Calculation 2 (欧拉函数),布布扣,bubuko.com

hdu 3501 Calculation 2 (欧拉函数)

原文:http://www.cnblogs.com/bfshm/p/3707969.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!