现在的位置: 首页 > 编程语言 > 正文

欧拉函数及其延伸

2018年01月12日 编程语言 ⁄ 共 690字 ⁄ 字号 评论关闭

原文地址:欧拉函数及其延伸
作者:依然


欧拉函数:少于或等于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),证明于上述类似。
 
        欧拉公式的延伸:一个数的所有质因子之和是φ(x) * x / 2。
 
求欧拉函数的模板:

__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;
}
【上篇】
【下篇】

抱歉!评论已关闭.