快速幂

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
long long b,p,k,s,t;
int main()
{
    cin>>b>>p>>k;
    cout<<b<<"^"<<p<<" mod "<<k<<"=";
    s=b%k;
    t=1;
    for (int i=2;i<=p;i++)
    {
        s=s*b%k;
        if (s==b%k) break;
        t++;
    }
    p=p%t;s=1;
    if (p==0) p=t;
    for (int i=1;i<=p;i++)
    s=s*b%k;
    cout<<s;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long ans=1,i,j,k,m,n,b,p;
    scanf("%lld%lld%lld",&b,&m,&p);
    printf("%lld^%lld mod %lld=",b,m,p);
    while(m>0){
        if(m%2==1)
            ans=ans*b%p;
        b=b*b%p;
        m=m>>1;
    }
    printf("%lld",ans%p);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
long long b,a,p,k,ans=1,c;
int main()
{
    scanf("%d%d%d",&b,&p,&k);
    a=b;c=p;
    while(p>0)//快速幂
    {
        if(p%2!=0)
            ans=ans*b%k;//如果p为单数，乘到ans里面去，然后取模
        b=b*b%k;//每次运算都取模
        p=p>>1;    //用位运算除2，可能会快一点
    }
    printf("%d^%d mod %d=%d",a,c,k,ans);//输出
    return 0;
}