A^B Mod C （快速幂）

3 5 8

3

#include<bits/stdc++.h>

using namespace std;

long long int pow_mod(long long int a, long long int k, long long int c)
{
    long long int ans = 1;
    while(k)
    {
        if(k % 2) ans *= a;
        a = (a * a) % c;
        k /= 2;
        ans %= c;
    }
    return ans;
}

int main()
{
    long long int a, b, c;
    scanf("%lld %lld %lld", &a, &b, &c);
    a %= c;
    printf("%lld\n",pow_mod(a,b,c));
    return 0;
}