加载中…
个人资料
依然
依然
  • 博客等级:
  • 博客积分:0
  • 博客访问:378,268
  • 关注人气:191
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

欧拉函数及其引伸

(2011-05-03 21:17:59)
标签:

acm

欧拉函数

延伸

校园

分类: 学习资料

欧拉函数:小于或等于n的数中,与n互质的数的数目。(互质:最大公因数为1)

通式:φ(x) = x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),,其中p1, p2……pn为x的所有质因数,x是不为0的整数。φ(1) = 1。

例如:12 = 2*2*3, 那么φ(12) = 12*(1-1/2)*(1-1/3) = 4,因为1,5,7,11均和12互质。

       8 = 2*2*2, 那么φ(8) = 8*(1-1/2) = 4,因为1,3,5,7均和8互质。

       7 = 7,     那么φ(7) = 7*(1-1/7) = 6,因为1,2,3,4,5,6均和7互质。

      21 = 3*7,   那么φ(21) = 21*(1-1/3)*(1-1/7) = 12....

性质:1:若n是质数p的k次幂,φ(n)=p^k-p^(k-1)=(p-1)p^(k-1),因为除了p的倍数外,其他数都跟n互质。

    2:欧拉函数是积性函数,若m,n互质,φ(mn)=φ(m)φ(n)。如15和8互质,则 φ(120)=φ(15)φ(8)。

    3:当n为奇数时,φ(2n)=φ(n), 如φ(30)=φ(15),证明于上述类似。

 

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

例子:12 = 2*2*3, 那么φ(12) * x / 2 = 24,因为1,5,7,11均和12互质,它们的和为24。

       8 = 2*2*2, 那么φ(8) * x / 2 = 16,因为1,3,5,7均和8互质,它们的和为16。

       7 = 7,     那么φ(7) * x / 2 = 21,因为1,2,3,4,5,6均和7互质,它们的和为21。

      21 = 3*7,   那么φ(21) * x / 2 = 126....

 

求欧拉函数的模板:

__int64 phi(__int64 n){
    __int64 ans = n;
    for(int i = 2; i * i <= n; i ++)
        if(n % i == 0){
            ans -= ans / i;
            while(n % i== 0)
                n /= i;
        }
    if(n > 1) ans -= ans / n;
    return ans;
}

0

阅读 评论 收藏 转载 喜欢 打印举报
已投稿到:
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 不良信息反馈 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有