欧拉降幂

结论

把结论记录下，其实费马小定理就是欧拉降幂的一个衍生

\(\phi(x)\)表示\(x\)的欧拉函数

对于非特殊的情况下

\[ a^b=\left\{ \begin{array}{rcl} a^b & & {b<\phi(m)}\\ a^{b\;mod\;\phi(m)+\phi(m)} & & {b \geq \phi(m)}\\ \end{array} \right. \]

对于\(\gcd(a,m)=1\)

\(a^b=a^{b\;mod\; \phi(m)}\)

而\(\phi(质数)=质数-1\)

所以就可以得到费马小定理的结论\(a^b=a^{b\;mod\;(m-1)}\)

注意对于非特殊情况的\(+\phi(m)\)不能省略

模板题

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a,m,b;
int get(int x){
    ll ans=x;
    for(ll i=2;i*i<=x;i++){
        if(x%i==0){
            ans=ans/i*(i-1);
            while(x%i==0){
                x=x/i;
            }
        }
    }
    if(x!=1){
        ans=ans/x*(x-1);
    }
    return ans;
}
int qpow(int a,int b){
    ll ans=1,base=a;
    while(b){
        if(b&1) ans=ans*base%m;
        base=base*base%m;
        b=b>>1;
    }
    return ans;
}
int main(){
   scanf("%d%d",&a,&m);
   int mod=get(m);
   char ch;
   bool flag=0;
   while((ch=getchar())!=-1){
        if(ch==' ') continue;
        b=b*10+ch-'0';
        if(b>mod) b%=mod,flag=1;
   }
   if(flag) b+=mod;
   printf("%d\n",qpow(a,b));
   return 0;
}