【算法学习笔记】31：试除法分解质因数及求解欧拉函数

试除法分解质因数

原理

在$O(\sqrt{n})$时间内可以对$n$分解质因数，原理就是从最小质因数2开始遍历，第一个遍历到的因数就是2，一定是一个质因数。

每次都从$n$里将遇到的质因子除干净，那么下次遇到的因数$i$也一定是一个质因数。

可以用反证法：如果下次遇到的因数$i$不是一个质因数，那么说明有$<i$的另一个质因数$j$，那么因为我们每次遇到质因数都会从$n$里除干净，所以$j<i$一定在过去的某一轮被除干净了，矛盾，证毕。

这个遍历只需要在$i\cdot i\le n$的情况下继续就可以了，因为一旦$i\cdot i>n$，最后剩下的要么$n$是1，要么$n$是最后一个质因数（且出现了一次方），一定不存在其它没遍历到的质因数了。

可以用反证法：假如$n$还是一个合数，还存在没遍历到的质因子$i$，那么$\frac{n}{i}$也一定是一个因数，这个因数的任何一个质因子都$<i$，又一定从$n$里被剔除过了，矛盾，证毕。

最后记得判断一下$n$是不是剩下一个一次方的最大质因子，也就是$n$如果不是1就是最后的那个质因数。

例题：AcWing 867. 分解质因数

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    
    while (t -- ) {
        int n;
        cin >> n;
        for (int i = 2; i * i <= n; i ++ ) {
            int mi = 0;
            while (n % i == 0) {
                mi ++ ;
                n /= i;
            }
            if (mi) cout << i << " " << mi << endl;
        }
        if (n != 1) cout << n << " " << 1 << endl;
        cout << endl;
    }
    
    return 0;
}

试除法求解欧拉函数

利用试除法分解质因数，同样可以解决欧拉函数的计算问题。

定义与计算公式

欧拉函数$\varphi (n)$表示从1到n中和n互质的数字的个数，两个数字除了1没有其它公因数就是互质。比如从1到6之间和6互质的数字只有1和5，所以$phy(6)=2$。

设$n$分解质因数之后的结果是：
$$n=p_1^{{\alpha }_1}+p_2^{{\alpha }_2}+..+p_k^{{\alpha }_k}$$
那么欧拉公式的计算公式是：
$$\varphi (n)=n\cdot (1-\frac{1}{p_1})\cdot (1-\frac{1}{p_2})\cdot ...\cdot (1-\frac{1}{p_k})$$

证明

思路是用容斥原理。假设$n$的质因子只有$p_1$到$p_k$，那么根据欧拉函数的定义，只要从1到n中去掉$p_1$到$p_k$所有数的倍数，最后剩下的就是和$n$互质的数。

第一步：减去所有$p_1$到$p_k$的倍数

$$n-\lfloor \frac{n}{p_1}\rfloor -\lfloor \frac{n}{p_2}\rfloor -...-\lfloor \frac{n}{p_k}\rfloor$$

但是因为某个$p_i$的倍数同时可能也是$p_j$的倍数，所以直接去掉每个数的倍数就会存在多去除的情况，因此就要把多去掉的部分加回来。

第二步：加上所有$p_i\cdot p_j$的倍数

$$+\lfloor \frac{n}{p_1\cdot p_2}\rfloor +\lfloor \frac{n}{p_1\cdot p_3}\rfloor +...+\lfloor \frac{n}{p_{k-1}\cdot p_k}\rfloor$$

进而考虑，如果有一个数是$p_i$、$p_j$、$p_k$的倍数，那么在第一步会被$p_i$、$p_j$、$p_k$各减去一次，第二步会被$p_i\cdot p_j$、$p_j\cdot p_k$、$p_i\cdot p_k$各加上一次，减掉三次加上三次，没有加没有减，所以下一步要减去所有同时是三个数的倍数。

第三步：减去所有$p_i\cdot p_j\cdot p_k$的倍数

$$-\lfloor \frac{n}{p_1\cdot p_2\cdot p_3}\rfloor -\lfloor \frac{n}{p_1\cdot p_2\cdot p_4}\rfloor -...-\lfloor \frac{n}{p_{k-2}\cdot p_{k-1}\cdot p_k}\rfloor$$

所以接下来就是加上所有四个质数乘积分之$n$，再减去所有五个质数乘积分之$n$…

将前面给出的欧拉公式的计算公式展开，就可以发现和这个加加减减的式子是相等的，即：
$$\begin{array}{rl}\varphi (n)& =n-\lfloor \frac{n}{p_1}\rfloor -\lfloor \frac{n}{p_2}\rfloor -...-\lfloor \frac{n}{p_k}\rfloor \\ & +\lfloor \frac{n}{p_1\cdot p_2}\rfloor +\lfloor \frac{n}{p_1\cdot p_3}\rfloor +...+\lfloor \frac{n}{p_{k-1}\cdot p_k}\rfloor \\ & -\lfloor \frac{n}{p_1\cdot p_2\cdot p_3}\rfloor -\lfloor \frac{n}{p_1\cdot p_2\cdot p_4}\rfloor -...-\lfloor \frac{n}{p_{k-2}\cdot p_{k-1}\cdot p_k}\rfloor \\ & ...\\ & =n\cdot (1-\frac{1}{p_1})\cdot (1-\frac{1}{p_2})\cdot ...\cdot (1-\frac{1}{p_k})\end{array}$$

用眼睛看也能看出上下两个式子相等，首先把上面式子里的$n$提取出来，就是下面式子最外面的$n$。然后上面式子里的开头1就是下面式子乘法展开时候每一项选择前面的1的结果。上面式子里的$\frac{1}{p_i}$就是下面式子里只有$(1-\frac{1}{p_i})$选择了$-\frac{1}{p_i}$，其它式子都选择1的结果，因此符号一定是负的。上面式子里的$\frac{1}{p_i\cdot p_j}$就是下面式子里只有$(1-\frac{1}{p_i})$和$(1-\frac{1}{p_j})$选择了$-\frac{1}{p_i}$和$-\frac{1}{p_j}$，其它式子都选择1的结果，因此符号一定是正的。以此类推。

例题：AcWing 873. 欧拉函数

根据前面推导出的计算公式，只要用最开始的$n$，每次抠出质因数$p_i$，然后乘上$(1-\frac{1}{p_i})$，这里可以改写成除以$p_i$再乘以$p_i-1$，避免了浮点运算的同时也防止乘爆了溢出。

#include <iostream>

using namespace std;

int phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i ++ ) {
        if (n % i) continue;
        res = res / i * (i - 1);
        while (n % i == 0) n /= i;
    }
    if (n != 1) res = res / n * (n - 1);
    return res;
}

int main() {
    int t; cin >> t;
    
    while (t -- ) {
        int n; cin >> n;
        cout << phi(n) << endl;
    }
    
    return 0;
}

原文地址：https://blog.csdn.net/SHU15121856/article/details/145149826

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！