G14 剩余系 欧拉定理 扩展欧拉定理

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, m; char s[21110000];
LL get_phi(LL x)//欧拉函数：1~x与x互质的个数 
{
    LL ans = x;
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            ans = ans / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) ans = ans / x * (x - 1);
    return ans;
}
LL qpow(LL a, int b)
{
    LL ans = 1 % m; a = a % m;
    for (; b; b >>= 1)
    {
        if (b & 1) ans = ans * a % m;
        a = a * a % m;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld%s", &n, &m, s);
    LL phi = get_phi(m);
    LL b = 0, bk = 0;
    for (int i = 0; s[i]; i++)
    {
        b = b * 10 + s[i] - '0';
        if (b > phi) b %= phi, bk = 1;
    }
    if (bk) b += phi;
    LL ans = qpow(n, b);
    printf("%lld\n", ans);
    return 0;
}

G14 剩余系 欧拉定理 扩展欧拉定理

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m;char s[21110000];
LL get_phi(LL x)//欧拉函数：1~x与x互质的个数 
{
    LL ans=x;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            ans=ans/i*(i-1);
            while(x%i==0)x/=i;
        }
    }
    if(x>1)ans=ans/x*(x-1);
    return ans;
}
LL qpow(LL a,int b)
{
    LL ans=1%m;a=a%m;
    for(;b;b>>=1)
    {
        if(b&1)ans=ans*a%m;
        a=a*a%m;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld%s",&n,&m,s);
    LL phi=get_phi(m);
    LL b=0,bk=0;
    for(int i=0;s[i];i++)
    {
        b=b*10+s[i]-48;
        if(b>phi)b%=phi,bk=1;
    }
    if(bk)b+=phi;
    LL ans=qpow(n,b);
    printf("%lld\n",ans);
    return 0;
}