题解 P5091 【【模板】欧拉定理】
ouuan
2018-12-11 00:54:52
[数据加强版（需要使用龟速乘）](https://www.luogu.org/problemnew/show/U55950)
# 前置知识
证明定理：同余的基本性质、裴蜀定理、欧拉函数的定义/性质
在OI中使用定理：欧拉函数的计算
# 欧拉定理
## 结论
$\varphi(n)$ 表示小于等于 $n$ 的正整数中与 $n$ 互质的数的个数（欧拉函数）。
$$a\text{ 与 }m\text{ 互质时，}a^{\varphi(m)}\equiv1\mod m$$
## 证明
令 $x_{1..\varphi(m)}$ 表示小于等于 $m$ 的正整数中与 $m$ 互质的数，$p_i=a\times x_i$ 。
### 引理一
$$\forall i\ne j,p_i-p_j\not\equiv0\mod m$$
因为 $a$ 与 $m$ 互质，$x_i-x_j\ne0$ 且 $|x_i-x_j|<m$ ，所以 $a(x_i-x_j)\not\equiv0\mod m$ 。
### 引理二
$$\gcd(p_i\% m,m)=1$$
设 $p_i=km+r$，即 $ax_i-km=r$，由于 $\gcd(a,m)=1$，由[裴蜀定理](https://www.luogu.org/problemnew/show/P4549)可以得知 $r|x_i$，而 $x_i$ 与 $m$ 互质，所以 $r$ 与 $m$ 互质。
### 证明
由引理一可以得到，$p_i\% m$ 两两不同；由引理二可以得到，$p_i\% m$ 只有 $\varphi(m)$ 种不同的取值。
所以 $p_{1..\varphi(m)}\% m$ 和 $x_{1..\varphi(m)}$ 是一一对应的。
所以 $\prod\limits_{i=1}^{\varphi(m)}p_i\equiv\prod\limits_{i=1}^{\varphi(m)}x_i\mod m$，即 $a^{\varphi(m)}\prod\limits_{i=1}^{\varphi(m)}x_i\equiv\prod\limits_{i=1}^{\varphi(m)}x_i\mod m$ 。
所以 $a^{\varphi(m)}\equiv1\mod m$ 。
# 扩展欧拉定理
扩展欧拉定理无需 $a,m$ 互质。
## 结论
$$b\ge\varphi(m)\text{时},a^b\equiv a^{\left(b\mod\varphi(m)\right)+\varphi(m)}\mod m\quad\quad $$
## 证明
先取 $m$ 的一个质因数 $p$，令 $m=p^r\times s,gcd(p,s)=1$ 。
由欧拉定理得 $p^{\varphi(s)}\equiv1\mod s$，由欧拉函数的性质得 $\varphi(m)=\varphi(s)\times\varphi(p^r)$，所以 $p^{\varphi(m)}\equiv1\mod s$ 。
设 $p^{\varphi(m)}=ks+1$，那么 $p^{\varphi(m)+r}=km+p^r$，所以 $p^{\varphi(m)+r}\equiv p^r\mod m$ 。
当 $b\ge r$ 时，$p^b\equiv p^{b-r}\times p^r\equiv p^{b-r}\times p^{\varphi(m)+r}\equiv p^{b+\varphi(m)}\mod m$ 。
因为 $r\le\varphi(p^r)\le\varphi(m)$，所以当 $b\ge 2\varphi(m)$ 时 $b-\varphi(m)\ge r$，所以 $p^b\equiv p^{b-\varphi(m)}\mod m$，即 $p^b\equiv p^{(b\mod\varphi(m))+\phi(m)}\mod m$ 。
将 $a$ 质因数分解后乘起来，就可以得到 $a^b\equiv a^{(b\mod\varphi(m))+\varphi(m)}\mod m$ 。
需要注意的是，$b<\varphi(m)$ 时，$a^b\equiv a^{(b\mod\varphi(m))+\varphi(m)}\mod m$ 不一定正确。
# 参考代码
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
int a,b,m,temp,phi,ans=1;
bool flag;
int main()
{
int i;
char c;
scanf("%d%d",&a,&m);
temp=phi=m;
for (i=2;i*i<=m;++i) //计算phi
{
if (temp%i==0)
{
phi=phi-phi/i;
while (temp%i==0)
{
temp/=i;
}
}
}
if (temp>1)
{
phi=phi-phi/temp;
}
while (!isdigit(c=getchar())); //边读入b边取模
for (;isdigit(c);c=getchar())
{
b=b*10+c-'0';
if (b>=phi)
{
flag=true;
b%=phi;
}
}
if (flag) //只有b>=phi时才b+=phi
{
b+=phi;
}
for (i=20;i>=0;--i) //快速幂，不是必需的
{
ans=1ll*ans*ans%m;
if (b&(1<<i))
{
ans=1ll*ans*a%m;
}
}
cout<<ans;
return 0;
}
```