歐拉函式
記作$\varphi (n)$，表示小于等于n的數中與n互質的數的數目，（根據定義，phi(1)=1）
通式
$$\varphi(x)=x\prod_{i=1}^{n}(1-\frac{1}{p_{i}})$$其中$p_{i}$為$x$的所有質因數，
舉個例子：
比如$\varphi (12)$，把12質因數分解，$12=2\times 2\times 3$，得到了2和3兩個質因數，然后把2的倍數和3的倍數都刪掉
2的倍數：$2,4,6,8,10,12$
3的倍數：$3,6,9,12$
如果直接用$12 - 12/2 - 12/3$，那么6和12就重復減了，所以還要把即是2的倍數又是3的倍數的數加回來，所以這樣寫$12 - \frac{12}{2} - \frac{12}{3} + \frac{12}{2\times 3}$
然后變形一下
$$\varphi (12) = 12\times (1 - \frac{1}{2} - \frac{1}{3} + \frac{1}{6})= 12\times (1 - \frac{1}{2})\times (1 - \frac{1}{3}) $$
其實就是容斥原理，可以得到求解公式$$\varphi (n)=n\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times ...\times(1-\frac{1}{p_n})$$即$$\varphi(x)=x\prod_{i=1}^{n}(1-\frac{1}{p_{i}})$$其中$p_{1}......p_{n}$為n的素因子，
基本性質
（1）規定，$\varphi(1)=1$
（2）當$p$為質數，$\varphi(p^{k})=p^{k}-p^{k-1}$
（3）當$p$為質數，有$\varphi(p)=p-1$（4）歐拉函式是積性函式，也就是若$m$和$n$互質，則$\varphi(m\times n)=\varphi(m)\times \varphi(n)$
（5）當$p$為質數，如果$i\ mod\ p=0$，那么$\varphi (i\cdot p)=\varphi(i)\cdot p$證明：
根據$\varphi(x)=x\prod_{i=1}^{n}(1-\frac{1}{p_{i}})$，因為p是i的因子，所以$$\varphi(x\cdot p)=p\cdot x\prod_{i=1}^{n}(1-\frac{1}{p_{i}})=\varphi(x)\times p$$
（6）當$p$為質數，如果$i\ mod\ p\neq 0$，那么$\varphi (i\cdot p)=\varphi(i)\cdot (p-1)$
求解方法
直接求
使用通式直接求
//歐拉函式 int phi(int x) { int ans = x; for (int i = 2; i * i <= x; i++) { if (x % i == 0) { ans = ans / i * (i - 1);//先做除法，防止溢位 while (x % i == 0) x /= i; } } if (x > 1) ans = ans / x * (x - 1); return ans; }
復雜度是$O(\sqrt {n})$，如果要你求n個數的歐拉函式，復雜度是$O(n\sqrt {n})$，太慢了，
打表
埃氏篩思想
const int N = 100000 + 5; int phi[N]; void getPhi() { phi[1] = 1; for (int i = 2; i < N; i++) { if (!phi[i]) { for (int j = i; j < N; j += i) { if (!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i - 1); } } } }
時間復雜度和埃氏篩一樣，是$O(n\cdot loglogn)$，基本上滿足要求了，
線性篩法（歐拉篩思想）
借助歐拉函式的性質 的這兩條性質，我們還可以繼續優化一下，能夠做到復雜度$O(n)$
如果p是質數
（1）如果$i\ mod\ p=0$，那么$\varphi (i\cdot p)=\varphi(i)\cdot p$ （2）如果$i\ mod\ p\neq 0$，那么$\varphi (i\cdot p)=\varphi(i)\cdot (p-1)$（這條不用證明）const int N = 100000 + 5; int phi[N], prime[N], cnt = 0; void Euler() { phi[1] = 1; for (int i = 2; i < N; i++) { if (!phi[i]) { phi[i] = i - 1; prime[cnt++] = i; } for (int j = 0; j < cnt && i * prime[j] < N; j++) { if (i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j] - 1); else { phi[i * prime[j]] = phi[i] * prime[j]; break; } } } }
公式拓展
求$a^{b}\%p$
公式1：a，p互質，$a^{b}mod\ p=a^{b\% \varphi (p)}mod\ p$
根據 $a^{\varphi(p)} \equiv 1(mod\ p)$ （歐拉定理）
令 $$b\% \varphi (p)=t$$
則 $$b=k\cdot \varphi(p)+t\ (k=0,1,2,3...)$$
根據$$a^{\varphi(p)} \equiv 1(mod\ p)，a^{k\cdot \varphi(p) }mod\ p=(a^{\varphi(p)}mod\ p)^k=1$$
有$$a^{b}mod\ p=a^{k\cdot \varphi(p)+t}mod\ p=(a^{k\cdot \varphi(p)}mod\ p)*a^{t}mod\ p)mod\ p=a^{t}mod\ p$$ 所以 $$a^{b}mod\ p=a^{b\% \varphi (p)}mod\ p$$公式2：a，p不互質，$a^b\equiv a^{b\bmod \varphi(p)+\varphi(p)}\pmod p$
原理：
擴展歐拉定理
先挖個坑，過兩天再填，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138103.html
標籤：其他
上一篇：js 字串方法 和 陣列方法總覽
下一篇：二叉樹創立及遍歷