专栏文章

欧拉定理及扩展欧拉定理

llunivia
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqv24ok
此快照首次捕获于
2025/12/04 11:13
3 个月前
此快照最后确认于
2025/12/04 11:13
3 个月前
查看原文

整除

若 n mod p=0n\bmod p=0 则 p∣np|n，即 pp 可以被 nn 整除。

同余

若 a,ba,b 除于 pp 的余数相同，则记为 a≡b(modp)a\equiv b\pmod p。
通常情况下 p∈N∗p\in \mathbb{N^\ast}。

欧拉函数

φ(n)=∑i=1n[gcd⁡(i,n)=1]\varphi(n)=\sum\limits_{i=1}^{n}[\gcd(i,n)=1]。
φ(n)\varphi(n) 是积性函数，即满足 gcd⁡(n,m)=1,φ(nm)=φ(n)×φ(m)\gcd(n,m)=1,\varphi(nm)=\varphi(n)\times\varphi(m)。
单个欧拉函数求法：
φ(n)=n∏p∣n(1−1pi)\varphi(n)=n\prod\limits_{p|n}(1-\frac{1}{p_i})
CPP
int GetPhi(int n) {
  int ans = n;
  for(int i = 2;i * i <= n;i++) {
    if(n % i == 0) {
      ans = ans / i * (i - 1);
      while(n % i == 0) n /= i;
    }
  }
  if(n > 1) ans = ans / n * (n - 1);
  return ans;
}
证明：
设 a=pk(k∈N∗)a=p^k(k\in\mathbb{N^{\ast}}) 且 pp 是质数，则显然 aa 与 p,2p,…,pk−1pp,2p,\dots,p^{k-1}p 不互质，那么 φ(a)=pk−pk−1=pk(1−1p)\varphi(a)=p^k-p^{k-1}=p^k(1-\frac{1}{p})。
将 nn 唯一分解：
n=∏p∣npikin=\prod\limits_{p|n}p_i^{k_i}
则由积性函数得：
φ(n)=∏p∣nφ(piki)=∏p∣npiki(1−1pi)=n∏p∣n(1−1pi)\varphi(n)=\prod\limits_{p|n}\varphi(p_i^{k_i})=\prod\limits_{p|n}p_i^{k_i}(1-\frac{1}{p_i})=n\prod\limits_{p|n}(1-\frac{1}{p_i})
由于欧拉函数是积性函数，所以可以直接线性筛。
CPP
void Sieve(int siz,int p[],int phi[]) {
  int ncnt = 0;
  vector<int> vis(siz + 5);
  phi[1] = 1;
  for(int i = 2;i <= siz;i++) {
    if(!vis[i]) {
      p[++ncnt] = i;
      phi[i] = i - 1; 
    }
    for(int j = 1;j <= ncnt && i * p[j] <= siz;j++) {
      vis[i * p[j]] = 1;
      if(i % p[j] == 0) {
        phi[i * p[j]] = phi[i] * p[j];  //p[j]是i*p[j]的最小质因子
        break;
      }
      phi[i * p[j]] = phi[i] * phi[p[j]];
    }
  }
}

欧拉定理

若 gcd⁡(a,p)=1,aφ(p)≡1(modp)\gcd(a,p)=1,a^{\varphi(p)}\equiv 1\pmod p。
证明：
这里不包含 p=1p=1 的情况。
由于 φ(p)<p\varphi(p)<p，那么由上面的方法可得 a,2a,…,φ(p)aa,2a,\dots,\varphi(p)a 在模 pp 后互不相同。
∏i=1φ(p)Ai≡∏i=1φ(p)(Aia)(modp)\prod\limits_{i=1}^{\varphi(p)}A_i\equiv\prod\limits_{i=1}^{\varphi(p)}(A_ia)\pmod p φ(p)!≡φ(p)!aφ(p)(modp)\varphi(p)!\equiv \varphi(p)!a^{\varphi(p)}\pmod p aφ(p)≡1(modp)a^{\varphi(p)}\equiv 1\pmod p
特别的，当 pp 是质数时 φ(p)=p−1\varphi(p)=p-1，这就等价于 ap−1≡1(modp)a^{p-1}\equiv 1\pmod p 也就是费马小定理。

扩展欧拉定理

ab={ab mod φ(p),gcd⁡(a,p)=1ab,gcd⁡(a,p)≠1,b<φ(p),(modp)ab mod φ(p)+φ(p),gcd⁡(a,p)≠1,b≥φ(p)}a^b=\begin{Bmatrix}a^{b\bmod\varphi(p)},\gcd(a,p)=1\\a^b,\gcd(a,p)\ne1,b<\varphi(p),\pmod p\\a^{b\bmod\varphi(p)+\varphi(p)},\gcd(a,p)\ne1,b\ge \varphi(p)\end{Bmatrix}
简单来说就是若 gcd⁡(a,p)≠1,b≥φ(p)\gcd(a,p)\ne 1,b\ge\varphi(p) 则 ab≡ab mod φ(p)+φ(p)(modp)a^b\equiv a^{b\bmod\varphi(p)+\varphi(p)}\pmod p，这可用于 bb 很大时降次。
证明：
第一行式子由欧拉定理易得，不证。
第二与第三行：
我们取 m∣pm|p 且 mm 是质数，令 k=pmk=\frac{p}{m}。
由欧拉定理得：aφ(m)≡1(modm)a^{\varphi(m)}\equiv 1\pmod m。
因为 φ(m)∣φ(p)\varphi(m)|\varphi(p)，所以 aφ(p)≡1(modm)a^{\varphi(p)}\equiv 1\pmod m。
同时乘 aka^k，得到 aφ(p)+k≡ak(modp)a^{\varphi(p)+k}\equiv a^k\pmod p。
所以 ab≡ab−k+k≡aφ(p)+b(modp)a^b\equiv a^{b-k+k}\equiv a^{\varphi(p)+b}\pmod p。
因为 b≥φ(p)b\ge\varphi(p)，所以这个结论显然成立。
所以 ab≡aφ(p)+b(modp)a^b\equiv a^{\varphi(p)+b}\pmod p。
这就可以证明 nn 为质数的幂次方时的情况。剩余的用唯一分解定理即可简单证明。
模板
CPP
#include <bits/stdc++.h>
using namespace std;

#define int long long

template<class T>T Pow(T a,T b,T p,T ans=1){for(;b;b/=2){ans=((b&1?a:1)*ans%p),a=a*a%p;}return ans;}

int a,b,m,v;

inline int Read() {
  int x = 0,f = 0;
  char c = getchar();
  for(;c < '0' || c > '9';c = getchar());
  for(;c >= '0' && c <= '9';c = getchar()) {
    x = (x << 3) + (x << 1) + (c ^ 48);
    if(x >= v) f = 1;
    x %= v;
  }
  return f ? x + v : x;
}

int GetPhi(int n) {
  int ans = n;
  for(int i = 2;i * i <= n;i++) {
    if(n % i == 0) {
      ans = ans / i * (i - 1);
      while(n % i == 0) n /= i;
    }
  }
  if(n > 1) ans = ans / n * (n - 1);
  return ans;
}

signed main() {
  cin >> a >> m;
  v = GetPhi(m);
  b = Read();
  if(b < v) cout << Pow(a,b,m) << '\n';
  else cout << Pow(a,b % v + v,m) << '\n';
  return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...