题解 | 【模板】欧拉函数计算Ⅰ ‖ 朴素求值：试除法 #

$[模板+欧拉函数\varphi(x)]$

欧拉函数 $\varphi(x)$ 表示 $1,2,...,x$ 中与 $x$ 互质的数的个数

求 $\varphi(x)$ ：
首先将 $x$ 经行质因数分解： $x=p_{1}^{a_{1}}+p_{2}^{a_{2}}+...+p_{n}^{a_{n}}$ ，其中 $p_{1},p_{2},...,p_{n}$ 是 $x$ 不同的质因子

那么与 $x$ 互质的数不能被 $p_{1},p_{2},...,p_{n}$ 整除，从 $1$ 到 $x$ 一共有 $x$ 个数，那么：

第一步：减去能被单个质因子整除的数的个数

能被 $p_{1}$ 整除的数有 $\frac{x}{p_{1}}$ 个，能被 $p_{2}$ 整除的数有 $\frac{x}{p_{2}}$ 个，...，能被 $p_{n}$ 整除的数有 $\frac{x}{p_{n}}$ 个

所以第一步要减去 $\frac{x}{p_{1}} + \frac{x}{p_{2}} +...+\frac{x}{p_{n}}$

第二步：加上能被两个质因子整除的数的个数

能被 $p_{1} \times p_{2}$ 整除的数有 $\frac{x}{p_{1} \times p_{2}}$ 个，能被 $p_{1} \times p_{3}$ 整除的数有 $\frac{x}{p_{1} \times p_{3}}$ 个....

所以第二步要加上 $\frac{x}{p_{1} \times p_{2}} + \frac{x}{p_{1} \times p_{3}} + ...+\frac{x}{p_{n-1} \times p_{n}}$

第三步：减去能被三个质因子整除的数的个数

第四步：加上能被四个质因子整除的数的个数

.....

直至处理完 $n$ 个质因子

那么 $\varphi(x) = x - \sum_{i=1}^{n}{\frac{x}{p_{i}}} + \sum_{i=1}^{n}{\sum_{j=i+1}^{n}{\frac{x}{p_{i}p_{j}}}}-\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{\sum_{k=j+1}^{n}{\frac{x}{p_{i}p_{j}p_{k}}}}}....$

这个复杂的式子有一个非常优美的乘积形式：

$\varphi(x)= x\times(1-\frac{1}{p_{1}})\times(1-\frac{1}{p_{2}})\times...\times(1-\frac{1}{p_{n}})$ ，即 $\varphi(x) =x \times \prod_{i=1}^{n}(1 - \frac{1}{p_{i}})$

总代码:

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;



int work(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;
}
signed main(){
    HelloWorld;
    
    int q; cin >> q;
    while(q --){
        int x; cin >> x;
        cout << work(x) << endl;
    }
    return 0;
}

解释一下这行代码：

ans = ans / i * (i - 1);

这一步就是 $\times (1 - \frac{1}{p_{i}} ) = \times (\frac{p_{i}-1}{p_{}i})= \div p_{i} \times (p_{i} - 1)$

初始化 $ans=x$ ， $p_{i}$ 是 $x$ 的质因子，所以对于每一个 $p_{i}$ ， $ans$ 一定能够整除 $p_{i}$