欧拉函数_html-js-css

概述本博客转自：https://www.cnblogs.com/linyujun/p/5194170.html 欧拉函数，用φ(n)表示欧拉函数是求小于等于n的数中与n互质的数的数目可以先在1到n-1中找到与n不互质的数，然后把他们减掉比如φ(12) 把12质因数分解，12=2*2*3，其实就是得到了2和3两个质因数然后把2的倍数和3的倍数都删掉 2的倍数：2,4,6,8,10,1

本博客转自：https://www.cnblogs.com/linyujun/p/5194170.html

欧拉函数，用φ(n)表示

欧拉函数是求小于等于n的数中与n互质的数的数目

可以先在1到n-1中找到与n不互质的数，然后把他们减掉

比如φ(12)

把12质因数分解，12=2*2*3，其实就是得到了2和3两个质因数

然后把2的倍数和3的倍数都删掉

2的倍数：2,4,6,8,10,12

3的倍数：3,9,12

本来想直接用12 - 12/2 - 12/3

但是6和12重复减了

所以还要把即是2的倍数又是3的倍数的数加回来

所以这样写12 - 12/2 - 12/3 + 12/(2*3)

这叫什么，这叫容斥啊，容斥定理听过吧

比如φ(30)，30 = 2*3*5

所以φ(30) = 30 - 30/2 - 30/3 - 30/5 + 30/(2*3) + 30/(2*5) + 30/(3*5) - 30/(2*3*5)

但是容斥写起来好麻烦(￣.￣)

有一种简单的方法

φ(12) = 12*(1 - 1/2)*(1 - 1/3) = 12*(1 - 1/2 - 1/3 + 1/6)

φ(30) = 30*(1 - 1/2)*(1 - 1/3)*(1 - 1/5) = 30*(1 - 1/2 - 1/3 - 1/5 + 1/6 + 1/10 + 1/15 - 1/30)

你看( •?∀•? )，拆开后发现它帮你自动帮你容斥好

所以φ(30)的计算方法就是先找30的质因数

分别是2,3,5

然后用30* 1/2 * 2/3 * 4/5就搞定了

顺便一提，phi(1) = 1

 1 int phi(int x){ 2     int ans = x; 3     for (int i=2;i*i<=x;i++){ 4         if (x % i == 0){ 5             ans = (ans / i * (i - 1) ); 6             while (x % i == 0) 7                 x /= i; 8         } 9     }10     if (x>1){ // 防止x是质数11         ans = (ans / x * (x-1) );12     }13     return ans;14 }

这个的复杂度是O（√n），如果要你求n个数的欧拉函数，复杂度是O（n√n），这也太慢了

有更快的方法

跟埃筛素数差不多

 1 int phi[N]; 2  3 voID Euler(){ 4     phi[1] = 1; 5     for (int i=2;i<N;i++){ 6         if (!phi[i]){ 7             for (int j=i;j<N;j+=i){ 8                 if (!phi[j]) 9                     phi[j] = j;10                 phi[j] = phi[j] / i * (i - 1);11             }12         }13     }14 }

另一种，比上面更快的方法

需要用到如下性质

p为质数

1. phi(p)=p-1 因为质数p除了1以外的因数只有p，故1至p的整数只有p与p不互质

2. 如果i mod p = 0,那么 phi(i * p)=phi(i) * p （我不会证明）

3.若i mod p ≠0, 那么 phi( i * p )=phi(i) * ( p-1 ) （我不会证明）

 1 const int N = 1e5 + 10; 2  3 int phi[N],prime[N]; 4 int tot; 5  6 voID Euler(){ 7     phi[1] = 1; 8     for (int i=2;i<N;i++){ 9         if (!phi[i]){10             phi[i] = i-1;11             prime[tot++] = i;12         }13         for (int j=0;j<tot && 1ll*i*prime[j]<N;j++){14             if (i % prime[j]){15                 phi[i * prime[j]] = phi[i] * (prime[j] - 1);16             }17             else{18                 phi[i * prime[j]] = phi[i] * prime[j];19                 break;20             }21         }22     }23 }