欧拉定理
克尔苏加德
·
·
个人记录
费马小定理
\bullet\text{若 } p \text{ 是一个质数，且} a \text{ 不是 }p \text{ 的倍数}
\qquad a^{p - 1}\equiv 1(\mod p)
欧拉定理
\bullet\text{若 }a,p\text{ 互质}
\qquad a^{\psi(p)} \equiv 1(\mod p)
扩展欧拉定理
\bullet\text{当 }x\geq \psi(p)\text{ 时}
\qquad a^x\equiv a^{x \mod \psi(p) + \psi(p)}(\mod p)
这里的 \psi(p) 为 1\sim p 中与 p 互质的数的个数
首先来解决 a^n ,显然，快速幂
int qpow(int a,int b,int m){
int c = 1;
while (b){
if(b & 1 ) c = (long long)c * a % m;
a = (long long)a * a % m;
b >>= 1;
}
return c;
}
然后再来求 \psi(p)
这里有多种算法，此处主要介绍线性筛
先附上线性筛的代码
void ph(){
for(int i = 2 ; i <= INF ; i ++){
if(!notPrime[i]) prime[top++] = i; \\notPrime 标记一个数是否为质数，prime 则存储当前已经筛出的质数
int x;
for(int j = 1 ; (x = prime[j] * i) <= INF ; j ++){
notPrime[x] = 1;
if(i % prime[j] == 0) break;
}
}
return ;
}
这里要证明 2 个问题：
$\qquad 2.$ 没有漏筛
有点难理解为什么不会漏筛，此处就不做解释了
显然，若 $i$ 是一个质数， $phi[i] = i - 1
若 x 是一个合数，假设 prime[j] 是 x 的最小质因数 x 被 x^\prime 筛掉，即 x^\prime = \dfrac{x}{p}，考虑 2 种情况
\qquad 1.x\prime\mod p= 0
\qquad\quad phi[x] = x \times\prod\limits_{i=1}^{top}\dfrac{p_i - 1}{p_i}
\qquad\qquad\quad\;\;\;=prime[j]\times x^\prime\times\prod\limits_{i = 1}^{top}\dfrac{p_i - 1}{p_i}
\qquad\qquad\quad\;\;\;=prime[j]\times phi[x\prime]
$\qquad\quad phi[x] = phi[x\prime]\times (prime[j] - 1)$ 积性函数性质
```cpp
void ph(){
phi[1] = 1;
for(int i = 2 ; i <= INF ; i ++){
if(!notPrime[i]){
prime[top++] = i;
phi[i] = i - 1;
}
int x;
for(int j = 1 ; (x = prime[j] * i) <= INF ; j ++){
notPrime[x] = 1;
if(i % prime[j] == 0){
phi[x] = phi[i] * prime[j];
break;
}
phi[x] = phi[i] * (prime[j] - 1);
}
}
return ;
}
```
最后就是一个递归调用了
```cpp
int slove(int p){
if(p == 1) return 0;
return qpow(a,slove(phi[p]) + phi[p],p); //直接照公式来就可以了
}
```
------------
**举个栗子** 求 $2^{2^{2^{2^{2^{\cdots}}}}}\mod p$ 的值，一道裸题，把上面的串起来就可以了