快速幂模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func qmi(a, b, p int) int {
res := 1 % p
for b != 0 {
// 如果最低位是1的话,乘到答案中
if b&1 == 1 {
res = res * a % p
}
b >>= 1 // 去掉这位，看下一位
a = a * a % p // 准备下一位的要乘的数
}
return res
}
|
$1～n$ 中，和 n 互质的数的个数。
例如 $\varphi (6) = 2$, 因为只有 1,5 和 6 互质。
算术基本定理，n 可以分解成质因子的乘积
$$
n = p_1^{c_1}p_2^{c_2}p_3^{c_3} ... p_m^{c_m}
$$
则
$$
\varphi (n) = n*(1- \frac{1}{p_1}) * (1- \frac{1}{p_2}) * ... * (1- \frac{1}{p_k})
$$
第一种：分解质因数
因为我们要求 n 的 1-n 中的质因子，所以可以在分解质因数时，顺便按照公式进行乘质因子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
for k := 0; k < n; k++ {
a := rnI()
res := a
for i := 2; i <= a/i; i++ {
if a%i == 0 {
res = res * (i - 1) / i
for a%i == 0 {
a /= i
}
}
}
if a > 1 {
res = res * (a - 1) / a
}
fmt.Fprintln(ot, res)
}
|
第二种：线性筛法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
func euler() int {
phi[1] = 1 // 1的欧拉函数是1
for i := 2; i <= n; i++ {
if !st[i] {
primes[cnt] = i
cnt++
// i 是质数,那么它的欧拉函数是
phi[i] = i - 1
}
for j := 0; i*primes[j] <= n; j++ {
st[primes[j]*i] = true
if i%primes[j] == 0 {
// 情况2 -> i整除pirmes[j] , 说明primes[j] 肯定是i的质数中的质数，
// 欧拉公式和次数没关系，所以只是系数成了一个primes[j]
phi[i*primes[j]] = primes[j] * phi[i]
break
}
// 情况3
// 要乘1个primes[j] ,还要乘以（1-1/primes[j])
phi[i*primes[j]] = phi[i] * (primes[j] - 1)
}
}
res := 0
for i := 1; i <= n; i++ {
res += phi[i]
}
return res
}
|