一般大佬會(huì)給你證明，而菜鳥(niǎo)會(huì)教你怎么使用。

先擺上公式：

$a^b\equiv ?\begin{array}{ll}{a}^{bmod?(p)}& \text{g}cd(a,p)=1\\ a^b& \text{g}cd(a,p)=1,b<?(p)\\ a^{bmod?(p)+?(p)}& \text{g}cd(a,p)=1,b\ge ?(p)\end{array}(modp)$

歐拉降冪：

$a^b\equiv a^{bmod?(p)}gcd(a,p)=1$
適用范圍：
當(dāng)?shù)着c取模的數(shù)互質(zhì)，且b較大的時(shí)侯，我這句話用不到，直接擴(kuò)展歐拉降冪就好了，時(shí)間復(fù)雜度差不了多少。

擴(kuò)展歐拉定理：

$a^b\equiv \{\begin{array}{ll}{a}^b& \text{g}cd(a,p)=1,b<?(p)\\ a^{bmod?(p)+?(p)}& \text{g}cd(a,p)=1,b\ge ?(p)\end{array}(modp)$

總結(jié)：

用的時(shí)候我們只考慮擴(kuò)展的就可以了，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$bmod?(p)\equiv bmod?(p)+?(p)$

代碼：

這個(gè)代碼的優(yōu)點(diǎn)是，如果b太大，不能讀入的話也是可以處理的。
如果代碼需要多次計(jì)算的話，可以使用線性篩法，獲得歐拉函數(shù)的值。

#include <bits/stdc++.h> #define ll long long using namespace std; ll a,m,b;inline ll read(ll m){register ll x=0,f=0;char ch=getchar();while(!isdigit(ch)) ch=getchar();while(isdigit(ch)){x=x*10+ch-'0';if(x>=m) f=1;x%=m;ch=getchar();}return x+(f==1?m:0); }ll phi(ll n){ll ans=n,m=sqrt(n);for(ll i=2;i<=m;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; }ll fast_pow(ll a,ll b,ll p){ll ret=1;for(;b;b>>=1,a=a*a%p)if(b&1) ret=ret*a%p;return ret; }int main() {scanf("%lld%lld",&a,&m);b=read(phi(m));printf("%lld\n",fast_pow(a,b,m));return 0; }

題目：
洛谷模板題

總結(jié)

以上是生活随笔為你收集整理的数学--数论--欧拉降幂和广义欧拉降幂（实用好理解）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。