此题为经典的快速幂（废话）

（雾

我们来看一下快速幂的模板

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

时间复杂度为（log[HTML_REMOVED]2[HTML_REMOVED]n）

Ac Code

#include <cstdio>

using namespace std;
int a,b,p;


int main()
{
    scanf("%d%d%d",&a,&b,&p);
    int res=1 % p;
    //%p是因为要防止b=0即0次方，一旦b=0的话，就不会循环，导致输出的时候没有%p
    while(b)
    {
        if(b&1) res= res *1ll *a % p;
        //可能int会存不下，所以*1ll化为long long
        a = a * 1ll * a % p;
        b >>= 1;  //去掉个位
    }
    printf("%d", res);

    return 0;
}

最后普及两个小知识：

1.快速将一个数转换成long long 的形式 :

a=a*1ll //是1LL，不是111

2.移位：

1<[HTML_REMOVED]n[HTML_REMOVED]

1>>n=1 / 2[HTML_REMOVED]n[HTML_REMOVED]