【快速幂取模】fzu 1752 A^B mod C
KIDx 的解题报告
参考《算法艺术与信息学竞赛》：
题目：http://acm.fzu.edu.cn/problem.php?pid=1752
由于(1<=A,B,C<2^63)，所以要用到mul_mod二分求a*a，不然会溢出
原来的快速幂取模简单模板：
//求(a^b)%cint qmod (int a, int b, int c){int res = 1;for ( ; b; b >>= 1){if (b & 1)res = (LL)res * a % c; a = (LL)a * a % c;}return res;}
#include <iostream>using namespace std;#define ULL unsigned __int64ULL mul_mod (ULL a, ULL b, ULL c) //利用快速取幂模的思想求a*a%c和res*a%c，为了防止溢出{ULL res = 0;for ( ; b; b >>= 1){if (b & 1){res += a; //这两句换成 res = (res + a) % c 会很慢if (res >= c) res -= c;}a <<= 1; //这两句换成 a = (a + a) % c 也很慢if (a >= c) a -= c;}return res;}ULL qmod (ULL a, ULL b, ULL c){ULL res = 1;for ( ; b; b >>= 1){if (b & 1)res = mul_mod (a, res, c);a = mul_mod (a, a, c);}return res;}int main(){ULL a, b, c;while (~scanf ("%I64u%I64u%I64u", &a, &b, &c))printf ("%I64u\n", qmod (a%c, b, c)); return 0;}