尤拉函數

「觀前提醒」

「文章僅供學習和參考，如有問題請在評論區提出」

定義

尤拉函數的符號表示是 $\varphi (n)$ ，表示 $1\sim n$ 中和 $n$ 互質的數的個數。

例如，$\varphi (12) = 4$，即 $1,5,7,11$ 。

性質

若 $n$ 是質數，則 $\varphi (n) = n - 1$。

質數會和小於它本身的所有正整數互質，即 $n$ 與 $1 \sim n - 1$ 中所有數互質。
當 $n$ 是奇數時，$\varphi(2n) = \varphi(n)$。

只有這一種情況成立，並不是 $n$ 的偶數倍的意思。
如果 $n = p^{k}$，其中 $p$ 是質數，那麼

\[\begin{align} \varphi(n) & = p^{k} - p^{k - 1} \\ & = p^{k - 1}(p - 1) \\ & = p^{k}(1 - \frac{1}{p} ) \end{align} \]

$1 \sim n$ 中只有不包含質數 $p$，才會與 $n$ 互質。而包含質數 $p$ 的數為 $p$ 倍數，即 $1p,2p,3p,4p,...,p^{k - 1}p$ ，總共有 $p^{k - 1}$ 個。

所以去掉包含 $p$ 的數，就是和 $n$ 互質的數的個數，即 $\varphi(n) = p^{k} - p^{k - 1}$ 。

公式變形，就會有上述三個表示方式。
積性函數：若 $\gcd(a,b) = 1$，則 $\varphi(ab) = \varphi(a)\varphi(b)$ 。

計算公式推導

由唯一分解定理，

\[n = {\textstyle \prod_{i = 1}^{k}} p_{i}^{a_{i}} = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdot p_{3}^{a_{3}} ... \cdot p_{k}^{a_{k}} \]

$p_{i}$ 是 $n$ 的質因子

提醒：$\prod_{a}^{b} $ 是乘積運運算元號，代表 $a \sim b$ 所有數的乘積，即 $a \times (a + 1) \times ... \times b$ 。

那麼有，

\[\varphi(n) = \varphi({\textstyle \prod_{i = 1}^{k}}p_{i}^{a_{i}}) \]

因為對於任意的 $p_{i} ^{a_{i}}，p_{j}^{a_{j}}(1 \le i,j \le k)$ 都是互質的，所以用到上面的性質4：若 $\gcd(a,b) = 1$，則 $\varphi(ab) = \varphi(a)\varphi(b)$ 。那麼可以推出，

\[\begin{align} \varphi(n) & = \varphi({\textstyle \prod_{i = 1}^{k}}p_{i}^{a_{i}})\\ & = {\textstyle \prod_{i = 1}^{k}} \varphi(p_{i}^{a_{i}}) \end{align} \]

然後再根據性質3，推出

最後進行公式變形，可得

\[\begin{align} \varphi(n) & = \varphi({\textstyle \prod_{i = 1}^{k}}p_{i}^{a_{i}}) \\ & = {\textstyle \prod_{i = 1}^{k}} \varphi(p_{i}^{a_{i}}) \\ & = {\textstyle \prod_{i = 1}^{k}} p_{i}^{a_{i} - 1}(p_{i} - 1) \\ & = {\textstyle \prod_{i = 1}^{k}} p_{i}^{a_{i}}(1 - \frac{1}{p_{i}}) \\ & = {\textstyle \prod_{i = 1}^{k}} p_{i}^{a_{i}} \times {\textstyle \prod_{i = 1}^{k}}(1 - \frac{1}{p_{i}}) \\ & = n \times {\textstyle \prod_{i = 1}^{k}} \frac{p_{i} - 1}{p_{i}} \\ & = n \times \frac{p_{1} - 1}{p_{1}} \times \frac{p_{2} - 1}{p_{2}} \times ... \times \frac{p_{k} - 1}{p_{k}} \end{align} \]

公式進行整理，可得

\[\begin{align} \varphi(n) & = n \times {\textstyle \prod_{i = 1}^{k}} \frac{p_{i} - 1}{p_{i}} \\ & = n \times \frac{p_{1} - 1}{p_{1}} \times \frac{p_{2} - 1}{p_{2}} \times ... \times \frac{p_{k} - 1}{p_{k}} \end{align} \]

觀察公式就能發現，尤拉函數僅與 $n$ 及其質因子有關。

求尤拉函數

分解質因子法

思路：用試除法分解出 $n$ 的所有質因子，然後根據推導的公式求解一個數的尤拉函數。

時間複雜度：$O(\sqrt n )$

程式碼：

// 分解質因數求尤拉函數
int phi(int n) {
    int res = n;
    // 分解質因子
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            // 公式求值
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / i * (i - 1);
    
    return res;
}

篩法求尤拉函數

// 線性篩法求 1 ~ n 的 質數

const int N = 1e5 + 10;
int p[N], cnt;	// p[]儲存所有素數
bool st[N];	 // st[x]儲存x是否被篩掉

void get_primes(int n) {
	st[1] = true;
    
    for (int i = 2; i <= n; i++) {
        if (!st[i]) p[cnt++] = i;
        for (int j = 1; p[j] <= n / i; j++) {
            st[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }
}

思路：

觀察上面的線性篩質數的程式碼，我們可以再用一個 phi[] 來儲存每一個數的尤拉函數，即 $phi[i] = \varphi(i)$ 。

若 $i$ 是質數，根據性質1可得 $phi[i] = i - 1$ 。

而且線上性篩中，每個合數（非質數）都會被自身的最小質因子篩掉。那麼設 $p_{j}$ 是 $m$ 的最小質因子，根據線性篩，就想辦法讓 $m$ 通過 $m = p_{j} \times i$ 篩掉。

若 $i$ 能被 $p_{j}$ 整除，則 $i$ 就包含了 $m$ 的所有質因子。

若 $i$ 能被 $p_{j}$ 整除，說明 $p_{j}$ 也是 $i$ 的質因子。又因為 $p_{j}$ 也是 $m$ 的質因子，而且 $m = p_{j} \times i$ ，所以 $i$ 就包含了 $m$ 的所有質因子。

然後再根據推導的公式變形，得

\[\begin{align} \varphi(m) & = m \times {\textstyle \prod_{k = 1}^{S}} \frac{p_{k} - 1}{p_{k}} \\ & = p_{j} \times i \times {\textstyle \prod_{k = 1}^{S}} \frac{p_{k} - 1}{p_{k}} \\ & = p_{j} \times \varphi(i) \end{align} \]

根據推導公式，一個數得尤拉函數只與其本身和其質因子有關。

雖然 ${\textstyle \prod_{k = 1}^{S}} \frac{p_{k} - 1}{p_{k}}$ 是從 $\varphi(m)$ 推匯出來的，但是因為 $i$ 與 $m$ 的質因子相同，所以也可以被用來推匯出 $\varphi(i)$ 。
若 $i$ 不能被 $p_{j}$ 整除，則 $i$ 和 $p_{j}$ 是互質的。

因為 $p_{j}$ 是質數，除了 $p_{j}$ 本身，就沒有其他的質因子。若 $i$ 不能被 $p_{j}$ 整除，那麼 $i$ 和 $p_{j}$ 就沒有相同的質因子，那麼兩者就是互質的。

然後根據性質4和性質1進行公式變形，得

\[\begin{align} \varphi(m) & = \varphi(p_{j} \times i) \\ & = \varphi(p_{j}) \times \varphi(i) \\ & = (p_{j} - 1) \times \varphi(i) \end{align} \]

總結上面的思路，就能得到所有的情況，

若 $i$ 是質數，得 $\varphi(i) = i - 1$ 。
若 $i$ 不是質數，說明已經被自己的質因子賦值了。
遍歷 $p[1 \sim cnt]$ ，
- 若 $i$ 能被 $p_{j}$ 整除，得 $\varphi(m) = p_{j} \times \varphi(i)$ ，並退出遍歷。
- 若 $i$ 不能被 $p_{j}$ 整除，得 $\varphi(m) = (p_{j} - 1) \times \varphi(i)$ 。

時間複雜度： $O(N)$

程式碼：

const int N = 1e5 + 10;
int p[N], cnt;	// p[] 儲存所有素數
int phi[N];	// phi[x] 儲存 x 的尤拉函數值
bool st[N];	// st[x] 儲存 x 是否被篩掉

// 線性篩法求尤拉函數
void get_phi(int n) {
    phi[1] = 1;
    st[1] = true;
    
    for (int i = 2; i <= n; i++) {
        // 沒有被篩過，說明是質數
        if (!st[i]) {
            p[cnt++] = i;
            phi[i] = i - 1;
        }
        
        for (int j = 0; p[j] <= n / i; j++) {
            int m = i * p[j];
          	st[m] = true;
            // 判斷是否能整除，然後根據公式賦值
            if (i % p[j] == 0) {
                phi[m] = p[j] * phi[i];
                break;
            } else phi[m] = (p[j] - 1) * phi[i];
        }
    }
}

參考資料

尤拉函數 - OI Wiki (oi-wiki.org)：https://oi-wiki.org/math/number-theory/euler/

【RSA原理2】淺談--什麼是尤拉函數韋_恩的部落格-CSDN部落格：https://blog.csdn.net/qq_42539194/article/details/118514310

董曉演演算法 515 篩法求尤拉函數：https://www.bilibili.com/video/BV1VP411p7Bs