AcWing 873. 欧拉函数（单个欧拉模板）

题目链接

https://www.acwing.com/problem/content/875/

思路

我们可以通过容斥原理得到一个计算欧拉函数的公式： φ ( n ) = φ ( p 1 a 1 ) ∗ … ∗ φ ( p a a x ) φ(n)=φ(p_1^{a_1})∗…∗φ(p_a^{a_x}) φ(n)=φ(p1a1​​)∗…∗φ(paax​​)

= ( p 1 a 1 − p 1 a 1 − 1 ) ∗ … ∗ ( p x a x − p x a x − 1 ) =(p_1^{a_1}−p_1^{a_1−1})∗…∗(p_x^{a_x}−p_x^{a_x−1}) =(p1a1​​−p1a1​−1​)∗…∗(pxax​​−pxax​−1​)

= p 1 a 1 ∗ ( 1 − 1 p 1 ) ∗ p 2 a 2 ∗ ( 1 − 1 p 2 ) ∗ … ∗ p x a x ∗ ( 1 − 1 p x ) =p_1^{a_1}∗(1−\frac{1}{p1})∗p_2^{a_2}∗(1-\frac{1}{p2})∗…∗p_x^{a^x}∗(1−\frac{1}{p_x}) =p1a1​​∗(1−p11​)∗p2a2​​∗(1−p21​)∗…∗pxax​∗(1−px​1​)

= n × ∏ i = 1 x ( 1 − 1 p i ) =n\times \begin{matrix} \prod_{i=1}^x (1-\frac{1}{p_i}) \end{matrix} =n×∏i=1x​(1−pi​1​)​ 然后我们只需要做一个试除法将这个质因子筛出来即可，防止溢出，我们先做除法，后做乘法

代码

#include 
using namespace std;
#define ll long long

int n;

ll ourla(ll x){
    ll res = x;
    for(ll i = 2;i  1) res = res / x * (x - 1);
    return res;
}
int main()
{
    ll x;
    scanf("%d",&n);
    while(n--){
        scanf("%lld",&x);
        printf("%lld\n",ourla(x));
    }
    
    
    return 0;
}