4:整数模

总时间限制: 

5000ms 

内存限制: 

32768kB

描述

a除以m的余数称为a对于m的模。求ap对于m的模。

输入

输入数据中含有一些数据组，每个数据组含有a、p、m（0＜a,p＜2^32，1≤m＜2^16）三个整数。若三个数都为0，则输入结束。

输出

针对每组a,p,m，以一行的形式输出ap对于m的模。

样例输入

3 18132 170 0 0

样例输出

13

解析:

对大整数求余数一般是在对其进行所有加减和乘运算时就求模。a mod m表示a对于m的模。 那么a^p mod m = [ a^(p-1) mod m * a ] mod m 也就是可以求 a mod m = t然后求 (t * a)mod m =t ,反复

代码如下:

#include #include #include using namespace std; int main() { long long int a,p,m; while(cin>>a>>p>>m && a!=0 && p!=0 && m!=0) { long long int r=1,n; for(int i=1;i<=p;i++) { r=(r*a)%m; } cout<
但是，依旧不是最好的方法

更好的用幂取模算法，若p是偶数，a^p mod m =[ a^(p/2) mod m ] ^2 mod m这可以每次把问题的规模降一倍。递归实现幂取模

#include #include #include using namespace std; long long qiuyu(long long di,long long zhi,long long mod); int main() { long long a,p,m,r; while(cin>>a>>p>>m && a!=0 && p!=0 && m!=0) { if(m!=1) { r=qiuyu(a,p,m); cout<