log(n)求a^n%b

/*
输入a,n,k（1<=a,n<=1,000,000,000 1<=k<=10,000 ，
注意：有多组测试数据，请用EOF标志判断结束输入）：
2 32 5
2 30 5

输出(a^n)%k的结果（a的n次方被k除的余数）：
1
4
*/
#include <stdio.h>
#include <iostream.h>

#ifdef _DEBUG
typedef __int64 int64_t;
#else
typedef long long int64_t;
#endif

/*
 *直接利用求余公式是会TLE的，因为n最大有10^9
 *这里的算法是对n进行2分，即n/2
 *n只有两种可能：n = 2x + 1(n是奇数) 或 n = 2x(n是偶数)
 *所以a^n = a^(2x+1) 或 a^(2x)
 *分别考虑：
 *A. n = 2x时
 *a^n = a^(2x) = (a^2)^x = (a*a)^x
 *所以令b = a*a，上式变化为a^n = b^x，并将b,x分别赋给a,n，继续迭代下去
 *B. n = 2x+1时
 *a^n = a^(2x+1) = a^(2x) * a = (a*a)^x * a
 *令 b = a*a,上式变化为a^n = b^x * a，其中a单独处理， 并将b,x分别赋给a,n，继续迭代下去
*/
int mod(int64_t a, int64_t n, int64_t k){
    int64_t r = 1;
    for (; n != 1; n >>= 1){ // n /= 2

        // n是奇数

        if ((n & 1) != 0)
            r = r * a % k; //单独处理

        a = a * a % k; // a = b = a*a

    }
    return int(r * a % k);
}

int main()
{
    int a, n, k;
    while (scanf("%d %d %d", &a, &n, &k) == 3){
        printf("%d\n", mod(a, n, k));
    }
    return 0;
}