P5091 【模板】欧拉定理(欧拉降幂)

P5091 【模板】欧拉定理

以上3张图是从这篇 博客 里盗的，讲的比较清楚。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=20001006;

ll mod(ll x,ll p)

{

	return x>=p?x%p+p:x%p;

}

ll phi(ll x)

{

    ll res=x,a=x;

    for(ll i=2;i*i<=x;++i)

    {

        if(a%i==0)

        {

            res=res/i*(i-1);

            while(a%i==0)a/=i;

        }

    }

    if(a>1)res=res/a*(a-1);

    return res;

}

ll qpow(ll n,ll k,ll p)

{

    ll base=n,res=1;

    while(k)

    {

        if(k&1)res=res*base%p;

        base=base*base%p;

        k>>=1;

    }

    return res;

}

ll a,c,p,sum,len;

char b[N];

int main()

{

	scanf("%lld%lld%s",&a,&c,b);

    len=strlen(b);p=phi(c);sum=0;

    for(int i=0;i<len;++i)

        sum=mod((b[i]-'0'+sum*10),p);

    printf("%lld\n",qpow(a,sum,c));

    return 0;

}