今天我刷题了吗
搜索文档…
欧拉函数

欧拉函数

欧拉函数(Euler's totient function),即
φ(n)\varphi(n)
,表示的是小于等于
nn
nn
互质的数的个数。
比如说
φ(1)=1\varphi(1) = 1
nn
是质数的时候,显然有
φ(n)=n1\varphi(n) = n - 1
利用唯一分解定理,我们可以把一个整数唯一地分解为质数幂次的乘积。
n=i=1npikin = \prod_{i=1}^{n}p_i^{k_i}
,其中
pip_i
是质数,那么
φ(n)=n×i=1spi1pi\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}

欧拉定理

gcd(a,m)=1\gcd(a, m) = 1
,则
aφ(m)1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}

费马小定理

pp
为素数,
gcd(a,p)=1\gcd(a, p) = 1
,则
ap11(modp)a^{p - 1} \equiv 1 \pmod{p}

威尔逊定理

(p1)!1(modp)(p-1)!\equiv-1\pmod{p}
pp
为质数,则
pp
可整除
(p1)!+1(p-1)!+1

筛法求欧拉函数

1
void phi_table()
2
{
3
for (int i = 1; i < maxn; i++) {
4
phi[i] = i;
5
}
6
for (int i = 2; i < maxn; i++) {
7
if (phi[i] == i) {
8
for (int j = i; j < maxn; j += i) {
9
phi[j] = phi[j] / i * (i - 1);
10
}
11
}
12
}
13
}
Copied!

Pollard Rho 算法求欧拉函数

1
ll get_phi(int n)
2
{
3
ll res = 1;
4
for (int i = 2; i <= sqrt(n); i++) {
5
if (n % i == 0) {
6
n /= i;
7
res *= i - 1;
8
while (n % i == 0) {
9
n /= i;
10
res *= i;
11
}
12
}
13
}
14
if (n > 1) {
15
res *= n - 1;
16
}
17
return res;
18
}
Copied!
最近更新 11mo ago
复制链接