快速幂算法，顾名思义，就是进行幂运算，http://acm.hdu.edu.cn/showproblem.php?pid=1061 这是hdu经典的一道题，如果我在接下来的解析中写的不好，也请大家指点。 hdu这道题，他要求我们算出每个正整数的个位数， 这里我先上代码，按题要求，我们先输入t，即接下去我们要进行测试t个例子，t– 的同时我们输入我们要取个位的数字，然后打印go，重点来咯，go自定义函数，就是进行取模运算的关键，因为无论输入什么数字，我们取模后他的个位都不会发生变化，因此，我们在开头就定义了一个a，先将他取模，这样，更是减少了算法的复杂度，b就是a的b次，while(b)相当于当b！=0的时候，也就是当b次不为0时，我们就可以进行幂运算啦， 从这个图片就能看出，当为奇数的时候，他会剩下最后一个单独的A，因此ans=（ans*a）就由此得出，这句话就是进行奇数运算的时候所要进行的，最后（a*a）%c ，a*a就是要求进行的b次运算，最后取模，得到个位数，进行到n-2次的时候 b因为b/2变为1，得出b次的最后一个个位数，这是回到if (b % 2 == 1) ans = (ans*a) % c; 得出最后一个个位数，返回到主函数main中，就可以得出答案拉。 另外，在这里指出一个小技巧，当我们进行b次相乘取模的时候，我们会有趣的发现，在我们算出几个余数之后，接下去的余数会无限有循环的计算下去。例如2=2，（2*2）=4，（2*2*2）=8，（2*2*2*2）=16，（2*2*2*2*2）=2 ，（2*2*2*2*2*2）=4.。。。。。。。 另外还有递归进行的幂算法， int qpow(int a,int n) { if(n == 0) return 1; int half = qpow(a,n/2); if(n%2) return half*half*a; return half*half; } int main() { printf(“%d\n”, qpow(2,10)); return 0; } 。
