正題

題目鏈接:https://www.luogu.org/problem/P5091

---

題目大意

求$a^b\mathrm{m}\mathrm{o}\mathrm{d}m$

---

歐拉定理及擴展

歐拉定理:

對于$(a,m)=1$那么有$$a^{\phi (m)}\equiv 1(modm)$$

擴展歐拉定理

$$a^b\equiv \{\begin{array}{c}{a}^{b\%\phi (p)+\phi (p)}(b>\phi (p))\\ a^{b\%\phi (p)}(b\le \phi (p))\end{array}(modp)$$

---

解題思路

然而本題是擴展歐拉定理，直接計算即可。

---

$code$

#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define ll long long using namespace std; ll a,p,phi,b; char c;bool flag; ll power(ll x,ll b,ll p) {ll ans=1;while(b){if(b&1) ans=ans*x%p;x=x*x%p;b>>=1;}return ans; } int main() {scanf("%lld%lld",&a,&p);phi=p;ll P=p;for(ll i=2;i*i<=p;i++)if(p%i==0){phi=phi*(i-1)/i;while(!(p%i)) p/=i;}if(p>1) phi=phi*(p-1)/p;while(!isdigit(c=getchar()));for(;isdigit(c);c=getchar()){b=b*10+c-'0';if(b>=phi)b%=phi,flag=1;}b+=phi*flag;printf("%lld",power(a,b,P)); }

總結

以上是生活随笔為你收集整理的P5091-[模板]欧拉定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。