欧拉函数
欧拉函数 ϕ ( n ) \phi(n) ϕ(n) 表示小于等于 n 的正整数中与 n 互质的数的个数。即：
ϕ ( n ) = ∣ { k ∈ Z + ∣ 1 ≤ k ≤ n , gcd ( k , n ) = 1 } ∣ \phi(n) = \left| \{ k \in \mathbb{Z}^+ \mid 1 \leq k \leq n, \gcd(k, n) = 1 \} \right| ϕ(n)=∣{k∈Z+∣1≤k≤n,gcd(k,n)=1}∣
当 n 是质数的时候,显然有 φ ( n ) = n − 1 。 \text{当 }n\text{ 是质数的时候,显然有 }\varphi(n)=n-1\text{。} 当 n 是质数的时候,显然有 φ(n)=n−1。
若 n = p k ,其中 p 是质数,那么 φ ( n ) = p k − p k − 1 。 \text{ 若 }n=p^k\text{,其中 }p\text{ 是质数,那么 }\varphi(n)=p^k-p^{k-1}。 若 n=pk,其中 p 是质数,那么 φ(n)=pk−pk−1。
求一个数的欧拉函数值，在质因数分解的同时求：
from math import isqrt
def euler_phi(n):
if n == 1:
return 1
else:
phi = n
max_n = isqrt(n)
for i in range(2, max_n + 1):
if n % i == 0:
phi -= phi // i
while n % i == 0:
n //= i
if n > 1:
phi -= phi // n
return phi
筛法求欧拉函数：
def euler_phi_sieve(n):
phi = list(range(n + 1)) # 初始化phi[i] = i
for i in range(2, n + 1):
if phi[i] == i:
for j in range(i, n + 1, i): # 遇到质数i 调整i所有倍数的欧拉函数值
phi[j] -= phi[j] // i
return phi
https://www.acwing.com/problem/content/description/4002/
d = gcd(a,m) = gcd(a+x,m)
d|a d|(a+x) --> d|x
我们定义 a ′ = a d , m ′ = m d , x ′ = x d ,那么根据最大公约数的性质,可得: gcd ( a ′ + x ′ , m ′ ) = 1 \begin{aligned}\text{我们定义 }a^{\prime}=\frac ad,m^{\prime}=\frac md,x^{\prime}=\frac xd\text{,那么根据最大公约数的性质,可得:}\gcd(a^{\prime}+x^{\prime},m^{\prime})=1\end{aligned} 我们定义 a′=da,m′=dm,x′=dx,那么根据最大公约数的性质,可得:gcd(a′+x′,m′)=1
而题目就转化为了: 求 [ a ′ , a ′ + m ′ − 1 ] 中有几个数与 m ′ 互质。 \text{而题目就转化为了: 求 }[a^{\prime},a^{\prime}+m^{\prime}-1]\text{ 中有几个数与 }m^{\prime}\text{ 互质。} 而题目就转化为了: 求 [a′,a′+m′−1] 中有几个数与 m′ 互质。
因为 [ 0 , a ′ − 1 ] 中在模 m 的意义下的余数与 [ m ′ , a ′ + m ′ − 1 ] 一样 \text{因为 }[0,a^{\prime}-1]\text{ 中在模 }m\text{ 的意义下的余数与 }[m^{\prime},a^{\prime}+m^{\prime}-1]\text{ 一样} 因为 [0,a′−1] 中在模 m 的意义下的余数与 [m′,a′+m′−1] 一样
所以转化为求 p h i ( m ′ ) phi(m') phi(m′)
from math import isqrt, gcd
def euler_phi(n):
if n == 1:
return 1
phi = n
for i in range(2, isqrt(n) + 1):
if n % i == 0:
phi -= phi // i
while n % i == 0:
n //= i
if n > 1:
phi -= phi // n
return phi
t = int(input())
for _ in range(t):
a, m = map(int, input().split())
d = gcd(a, m)
ans = euler_phi(m // d)
print(ans)
https://www.acwing.com/problem/content/203/
本题 n ，t 数据范围较小 --> 不然需要 筛法求欧拉函数 ， 甚至加上前缀和优化
from math import isqrt
def euler_phi(n):
if n == 1:
return 1
phi = n
for i in range(2, isqrt(n) + 1):
if n % i == 0:
phi -= phi // i
while n % i == 0:
n //= i
if n > 1:
phi -= phi // n
return phi
t = int(input())
for i in range(1, t + 1):
n = int(input())
cnt = 0
for k in range(n + 1):
cnt += euler_phi(k)
ans = cnt * 2 + 1
print(f"{i} {n} {ans}")
2023蓝桥杯省赛
https://www.lanqiao.cn/problems/3522/learning/
若m和n的质因数组成相同,m是n的k倍,则euler_phi(m)也是euler_phi(n)的k倍
euler_phi(a^b) = euler_phi(a) * a^(b-1)
mod = 998244353
a, b = map(int, input().split())
if a == 1:
exit(print(0))
from math import isqrt
def euler_phi(n):
if n == 1:
return 1
phi = n
max_n = isqrt(n)
for i in range(2, max_n + 1):
if n % i == 0:
phi -= phi // i
while n % i == 0:
n //= i
if n > 1:
phi -= phi // n
return phi
print(pow(a, b - 1, mod) * euler_phi(a) % mod)
欧拉降幂
幂次大于欧拉函数值 --> 欧拉降幂
a b ≡ { a b m o d φ ( m ) , gcd ( a , m ) = 1 , a b , gcd ( a , m ) ≠ 1 , b < φ ( m ) , ( m o d m ) a ( b m o d φ ( m ) ) + φ ( m ) , gcd ( a , m ) ≠ 1 , b ≥ φ ( m ) . a^b\equiv\begin{cases}a^{b\mathrm{~mod~}\varphi(m)},&\gcd(a,m)=1,\\a^b,&\gcd(a,m)\neq1,b<\varphi(m),&(\mathrm{mod~}m)\\a^{(b\mathrm{~mod~}\varphi(m))+\varphi(m)},&\gcd(a,m)\neq1,b\geq\varphi(m).&\end{cases} ab≡⎩ ⎨ ⎧ab mod φ(m),ab,a(b mod φ(m))+φ(m),gcd(a,m)=1,gcd(a,m)=1,b<φ(m),gcd(a,m)=1,b≥φ(m).(mod m)
模板
https://www.luogu.com.cn/problem/P5091
a, m, b = input().split() # 读取为字符串（b非常大）
a = int(a)
m = int(m)
from math import isqrt, gcd
def euler_phi(n):
if n == 1:
return 1
max_n = isqrt(n)
phi = n
for i in range(2, max_n + 1):
if n % i == 0:
phi -= phi // i
while n % i == 0:
n //= i
if n > 1:
phi -= phi // n
return phi
if m == 1:
exit(print(0))
phi = euler_phi(m)
flg = 0
b_mod_phi = 0
for digit in b:
b_mod_phi = (b_mod_phi * 10 + int(digit)) % phi
if len(b) > len(str(phi)):
flg = 1
elif len(b) == len(str(phi)):
flg = b >= str(phi)
if gcd(a, m) == 1:
int_b = b_mod_phi
else:
if flg:
int_b = b_mod_phi + phi
else:
int_b = int(b)
print(pow(a, int_b, m))
https://www.lanqiao.cn/problems/1155/learning/
n, m = map(int, input().split())
mod = 10**9 + 7
phi = mod - 1
x = 1
flg = 0
for i in range(1, m + 1):
x *= i
if x >= phi:
x %= phi
flg = 1
if flg:
x += phi
print(pow(n, x, mod))
END
*如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给