Problem Address：http://cstfs.gdufs.edu.cn:8080/JudgeOnline/problem.jsp?id=1064
是求a的b次幂。
但是数值很大，不过结果是对100求模。
首先把a对100求模。
然后仔细观察两位数的幂，因为只有两位，所以每20次方重复一次。
不过要注意第一次不适合这个规律，所以要出去幂为1之后再应用。
同样的只有一位数的时候也有相似的规律。
代码如下：
#include <iostream> using namespace std; int main() { int a,b,i,s; while(scanf("%d %d", &a, &b)!=EOF) { if (a==0 && b==0) break; a = a0; if (b==0) printf("1/n"); else if (b==1) printf("%d/n", a); else { s = a; b = (b-1) ; if (b==0) b=20; for (i=1; i<=b; i++) { s = (s*a)0; } printf("%d/n", s); } } return 0; }
p.s.刚刚查到过了六级。不过成绩不够理想。还得再考。好好加油！
+++++++++++++++++++++++++++++++++++时间分割线：以上为3月1日，以下为4月7日。
今天看了算法导论里的数论里面的一点东西，讲到了“运用反复平方法求数的幂”，大概就是这道题吧。
所以今晚回到宿舍写了一下，然后轻松A掉这道题。
所谓的“运用反复平方法求数的幂”，具体就去看算法导论吧。
求a^b mod n的值。
把b化为二进制数。
从高位开始。d=1。
从高位循环到低位。
d = (d * d) mod n。
如果此位二进制数为1，则 d = (d * a) mod n。
基本思想就是，该二进制代表着数的幂。如果读入下一位，表示把前面的数平方一次。如果该为1，则需要再乘多一个a。
还像没怎么讲明白……不懂的好好看书吧……
总之就是A掉了~
