题解：P5091 【模板】扩展欧拉定理
ACcepted917
·
·
题解
题解：P5091 【模板】扩展欧拉定理
题目传送门
欧拉函数 \varphi(n)
欧拉函数定义
欧拉函数（Euler's totient function），即 \varphi(n)，表示的是小于等于 n 并且 n 互质的正整数的个数。
形式化的讲，若集合 A=\{ x\ | \gcd(x,n)=1,x \in [1,n] \}，则 \varphi(n)=\operatorname{card}(A)，其中，\operatorname{card}(A) 表示有限集 A 中的元素个数（见人教 2019 版数学必修一第 15 页）。
举个例子，\varphi(7)=6，\varphi(10)=4。
欧拉函数实现
练习题目
方法一：暴力
循环 x 从 1 到 n，对于每一个 x，求 \gcd(x,n) 是否为 1，\varphi(n) 为 \gcd(x,n) 是 1 的次数。
#### 方法二：质因数分解
若
$$
n={p_1}^{a_1}\times {p_2}^{a_2}\times {p_3}^{a_3}\times \cdots \times {p_k}^{a_k},\forall p_i \in \text{prime}\ \ \text{and} \ \ \forall t_i \in \mathbb{N_+}
$$
由唯一分解定理，有
$$
\varphi(n)=n \prod_{i=1}^{k} \big \lparen 1-\dfrac{1}{p_i} \big \rparen =n \prod_{i=1}^{k} \dfrac{p_i-1}{p_i}
$$
[证明](https://oi-wiki.org/math/number-theory/euler-totient/#性质)如下：
代码如下：
```cpp
ll phi(ll n){
ll ans=n;
for(register int i=2;i*i<=n;i++){
if(!(n%i)){
while(!(n%i))n/=i;
ans/=i;
ans*=(i-1);
}
}
if(n>1){
ans/=n,ans*=(n-1);
}
return ans;
}
``````
时间复杂度 $\Theta(\sqrt{n})$。
欢迎大家在[练习题目](https://www.luogu.com.cn/problem/U587132)中提交。
## [费马小定理](https://oi-wiki.org/math/number-theory/fermat/#费马小定理)
费马小定理是欧拉定理的一个推论。
若 $p$ 为质数，$\gcd(a,p)=1$，且 $a,p \in \mathbb{Z}$，则
$$
a^{p-1} \equiv 1(\operatorname{mod} p)
$$
$$
\therefore a^b \equiv a^{b \operatorname{mod} (p-1)}(\operatorname{mod} p)
$$
证明见 [OI-Wiki](https://oi-wiki.org/math/number-theory/fermat/#证明)。
## [欧拉定理](https://oi-wiki.org/math/number-theory/fermat/#欧拉定理)
当 $a,n \in \mathbb{Z}$，且 $\gcd(a,n)=1$ 时有：
$$
a^{\varphi(n)} \equiv 1(\operatorname{mod} n)。
$$
所以
$$a^b \equiv a^{b \operatorname{mod} \varphi(n)}
(\operatorname{mod} n) $$
证明见 [OI-Wiki](https://oi-wiki.org/math/number-theory/fermat/#证明_1)。
当 $n \in \text{prime}$ 时，$\varphi(n)=n-1$，有
$$
a^b \equiv a^{b \operatorname{mod} (n-1)}(\operatorname{mod} n)
$$
即费马小定理，所以费马小定理是欧拉定理的一个推论。
## [拓展欧拉定理](https://oi-wiki.org/math/number-theory/fermat/#扩展欧拉定理)
本题重点。
$$
a^b \equiv \left\{ \begin{array}{rcl}
a^{b \operatorname{mod} \varphi(n)}, & \gcd(a,n)=1,\\
a^b & \gcd(a,n) \neq 1, &b<\varphi(n), \\
a^{(b \operatorname{mod} \varphi(n))+\varphi(n)}& \gcd(a,n) \neq 1,&b \geq \varphi(n),
\end{array}\right. \lparen \operatorname{mod} n \rparen.
$$
证明见 [OI-Wiki](https://oi-wiki.org/math/number-theory/fermat/#证明_2)
现在，前置知识讲完了，我们来梳理一下思路：
## 代码（共建美好洛谷，请勿抄袭）
注释代码是我的部分数论模版，供选用。
```cpp
#include<bits/stdc++.h>
using namespace std;
const unsigned long long N=6e5+5,M=6e5+5,prime=233317,Mod=212370440129904639,base=131;
typedef unsigned long long ll;
//#define int ll
ll n,p,a,b,m,mod;
#define inf 0x3f3f3f3f
#define mark 20250723222447
ll gcd(int x,int y){
int i,j;
if(x==0)return y;
if(y==0)return x;
for(i=0;(x&1)==0;i++)x>>=1;
for(j=0;(y&1)==0;j++)y>>=1;
if(j<i)i=j;
while(1){
if(x<y)x^=y,y^=x,x^=y;
if(0==(x-=y))return y<<i;
while(0==(x&1))x>>=1;
}
}
//ll x,y;
//inline void exgcd(ll a,ll b){
// if(!b){
// x=1,y=0;
// return;
// }
// exgcd(b,a%b);
// ll k;
// k=x;x=y;
// y=k-a/b*y;
//}
ll fpm(ll x,ll power,ll mod){//快速幂
x%=mod;
ll ans=1;
for(;power;power>>=1,(x*=x)%=mod)
if(power&1)(ans*=x)%=mod;
return ans;
}
//ll inv[3000005];
//ll niyuan(ll n,ll p,ll mod){
// inv[1]=1;
// for(register int i=2;i<=n;i++){
// inv[i]=(p-p/i)*inv[p%i]%mod;
// }
// return inv[n];
//}
//ll niyuan2(ll a,ll b){
// exgcd(a,b);
// x=(x+b)%b;
// return x;
//}
bool flag;
ll getll(ll mod){//读入部分
ll res=0;char ch;
while(!(ch>='0' && ch<='9') && ch!=EOF){
ch=getchar();
}
while((ch>='0' && ch<='9')){
res=(res<<3)+(res<<1)+(ch-'0');//等价于 res=res*10+(ch-'0')
if(res>=mod)flag=true;
res%=mod;
ch=getchar();
}
return res;
}
ll phi(ll n){//欧拉函数
ll ans=n;
for(register int i=2;i*i<=n;i++){
if(!(n%i)){
while(!(n%i))n/=i;
ans/=i;
ans*=(i-1);
}
}
if(n>1){
ans/=n,ans*=(n-1);
}
return ans;
}
ll phm=0;
ll exeut(ll a,ll b,ll m){//Extended Euler's theorem的自创缩写qwq
ll phm=phi(m);
if(gcd(a,m)==1)return fpm(a,b%phm,m);
if(!flag)return fpm(a,b,m);
else return fpm(a,(b%phm)+phm,m);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
a=getll(1e10);m=getll(1e10);
phm=phi(m);
b=getll(phm);
cout<<exeut(a,b,m);
return 0;
}
``````