这里我们需要两个公式：
这两个公式都不难理解，自己可以验证一下，3^4 = 9^2。
有了这两个公式之后我们就可以考虑思路了。
我们就以b为偶数来举例。
a^b%c = ((a^2)^b/2)%c;
在这里我们假设b/2还是偶数，那么
((a^2)^b/2)%c = (((a^2)^2)^(b/2)/2)%c;
代码如下：
#include <bits/stdc++.h>
using namespace std;
int quickMod(int a, int b, int c)
{
int ans = 1;
while (b)
{
if (b % 2 == 1)
ans = (ans * a) % c;
b /= 2;
a = (a * a) % c;
}
return ans;
}
int main()
{
int a, b, c;
while (~scanf("%d %d %d", &a, &b, &c))
{
printf("%d\n", quickMod(a, b, c));
}
return 0;
}
