欧拉函数

作者：

s.. , 2024-03-20 17:09:28 , 所有人可见 , 阅读 90

1.欧拉函数：
1~N中与N互质的数的个数被称为欧拉函数，记为ϕ(N)
若在算数基本定理中，N=p1^a1p2^a2……*pm^am，则：
ϕ(N)= N×(p1−1)/p1×(p2−1)/p2×…×(pm−1)/pm。

用的是容斥原理！！！
就是ϕ(N)的展开式。
欧拉函数与质数出现的次数无关。
2.互质：
互质数指的是在两个或多个整数中，它们的最大公约数仅为1的非零自然数。