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

欧拉函数

欧拉函数$\varphi (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}∣

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

$\text{ 若 }n=p^k\text{,其中 }p\text{ 是质数,那么 }\phi (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{array}{r}\text{我们定义 }{a}^{\prime }=\frac{a}{d},m^{\prime }=\frac{m}{d},x^{\prime }=\frac{x}{d}\text{,那么根据最大公约数的性质,可得:}\gcd (a^{\prime }+x^{\prime },m^{\prime })=1\end{array}$
$\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{ 一样}$

所以转化为求 $phi(m^{\prime })$

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{array}{llc}{a}^{b\mathrm{mod}\phi (m)},& \gcd (a,m)=1,& \\ a^b,& \gcd (a,m)\ne 1,b<\phi (m),& (\mathrm{mod}m)\\ a^{(b\mathrm{mod}\phi (m))+\phi (m)},& \gcd (a,m)\ne 1,b\ge \phi (m).& \end{array}$

---

模板

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
*如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给