题目链接
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−px1)
=
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−pi1)
然后我们只需要做一个试除法将这个质因子筛出来即可，防止溢出，我们先做除法，后做乘法
代码
#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;
}
