当前位置：首页 > news >正文

【算法】欧拉函数与欧拉降幂 python

news 来源：原创 2025/9/12 5:52:38

欧拉函数

欧拉函数 $\phi(n)$ 表示小于等于 n 的正整数中与 n 互质的数的个数。即：

$\phi(n) = \left| \{ k \in \mathbb{Z}^+ \mid 1 \leq k \leq n, \gcd(k, n) = 1 \} \right|$

$\text{当 }n\text{ 是质数的时候,显然有 }\varphi(n)=n-1\text{。}$

$\text{ 若 }n=p^k\text{,其中 }p\text{ 是质数,那么 }\varphi(n)=p^k-p^{k-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] = ifor i in range(2, n + 1):if phi[i] == i:for j in range(i, n + 1, i):  # 遇到质数i 调整i所有倍数的欧拉函数值phi[j] -= phi[j] // ireturn phi

https://www.acwing.com/problem/content/description/4002/

d = gcd(a,m) = gcd(a+x,m)
d|a d|(a+x) --> d|x
$\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}$
$\text{而题目就转化为了: 求 }[a^{\prime},a^{\prime}+m^{\prime}-1]\text{ 中有几个数与 }m^{\prime}\text{ 互质。}$
$\text{因为 }[0,a^{\prime}-1]\text{ 中在模 }m\text{ 的意义下的余数与 }[m^{\prime},a^{\prime}+m^{\prime}-1]\text{ 一样}$

所以转化为求 $p hi (m^{'})$

from math import isqrt, gcd
def euler_phi(n):if n == 1:return 1phi = nfor i in range(2, isqrt(n) + 1):if n % i == 0:phi -= phi // iwhile n % i == 0:n //= iif n > 1:phi -= phi // nreturn phit = 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 1phi = nfor i in range(2, isqrt(n) + 1):if n % i == 0:phi -= phi // iwhile n % i == 0:n //= iif n > 1:phi -= phi // nreturn phit = int(input())
for i in range(1, t + 1):n = int(input())cnt = 0for k in range(n + 1):cnt += euler_phi(k)ans = cnt * 2 + 1print(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 1phi = nmax_n = isqrt(n)for i in range(2, max_n + 1):if n % i == 0:phi -= phi // iwhile n % i == 0:n //= iif n > 1:phi -= phi // nreturn phiprint(pow(a, b - 1, mod) * euler_phi(a) % mod)

欧拉降幂

幂次大于欧拉函数值 --> 欧拉降幂

$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}$

模板

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 1max_n = isqrt(n)phi = nfor i in range(2, max_n + 1):if n % i == 0:phi -= phi // iwhile n % i == 0:n //= iif n > 1:phi -= phi // nreturn phiif 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)) % phiif 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 + phielse: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 - 1x = 1
flg = 0
for i in range(1, m + 1):x *= iif x >= phi:x %= phiflg = 1
if flg:x += phiprint(pow(n, x, mod))

END
*如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给

欧拉函数

欧拉降幂

模板

相关文章：