题目描述计算R B P m o d M R B^P \bmod MRBPmodM其中B BB、P PP、M MM可能很大。需要使用高效的算法。输入格式输入包含多个测试用例每个测试用例由三行组成B BB、P PP、M MM连续测试用例之间由一个空行分隔。B BB和P PP0 ≤ B , P ≤ 2147483647 0 \leq B, P \leq 21474836470≤B,P≤2147483647M MM1 ≤ M ≤ 46340 1 \leq M \leq 463401≤M≤46340输出格式对于每个测试用例输出一行包含计算结果。样例输入3 18132 17 17 1765 3 2374859 3029382 36123样例输出13 2 13195题目分析问题的本质这是一个快速幂取模问题。需要计算B P m o d M B^P \bmod MBPmodM其中指数P PP可能高达2 31 − 1 2^{31}-1231−1直接循环计算不可行。快速幂算法利用指数的二进制分解B P { ( B P / 2 ) 2 if P is even ( B P / 2 ) 2 × B if P is odd B^P \begin{cases} (B^{P/2})^2 \text{if } P \text{ is even} \\ (B^{P/2})^2 \times B \text{if } P \text{ is odd} \end{cases}BP{(BP/2)2(BP/2)2×B​ifPis evenifPis odd​每次将指数减半时间复杂度O ( log ⁡ P ) O(\log P)O(logP)。取模性质在乘法过程中取模( a × b ) m o d M ( ( a m o d M ) × ( b m o d M ) ) m o d M (a \times b) \bmod M ((a \bmod M) \times (b \bmod M)) \bmod M(a×b)modM((amodM)×(bmodM))modM因此可以在每一步都取模避免溢出。边界情况P 0 P 0P0B 0 1 B^0 1B01结果为1 m o d M 1 \bmod M1modMB m o d M 0 B \bmod M 0BmodM0结果为0 00参考代码// Big Mod// UVa ID: 374// Verdict: Accepted// Submission Date: 2016-06-25// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 递归快速幂取模longlongmod(longlongB,longlongP,longlongM){if(P1)returnB%M;if(P2)return(B*B)%M;longlongmmod(B,P/2,M);m(m*m)%M;if(P%21)m(m*(B%M))%M;returnm%M;}intmain(intargc,char*argv[]){longlongB,P,M;while(cinBPM){// 指数为 0 的特殊情况if(P0){cout1%Mendl;continue;}// 底数能被模数整除的情况if(B%M0){cout0endl;continue;}coutmod(B%M,P,M)endl;}return0;}