HDOJ 2035 人见人爱A ^ B

突然想起还有一份杭电ACM的PPT没看，翻出来看了下~发觉蛮有意思的，就是内容少了点。。。基本上是提纲，该总结的都自己来吧。╮(￣▽￣")╭

题目很简单，但也蛮经典的算术题。
输入两个数A,B。输出A ^ B的最右三位数。

核心思路：求 A的B次方 模1000，只需要求 A%1000 的 B次方。B通过降幂二分加速。
比如：（1123）^ 6 = (1000 + 123) ^ 6
多项式展开后，决定结果最后三位的是123 ^ 6
然后123 ^ 6 = (123 ^ 3) ^ 2

version 1.0  纯暴力

#include<cstdio>
int main()
{
int a,b,sum;
while(scanf("%d%d",&a,&b) && a){
sum = a;
for(int i = 1;i < b;i ++){
sum *= a;
if(sum >= 1000)sum %= 1000;
}
printf("%d\n",sum);
}
return 0;
}



优化之后，通过二分加速，int范围内的大数都可以接受。
version 1.1 递归




#include<cstdio>
int f(int a,int b)            //return the last three number
{
a %= 1000;
if(b == 1)return a;
if(b == 2)return (a * a) % 1000;
int t = f(a,b / 2);
if(b > 2 && b & 1)return (t * t * a) % 1000;      //if b is odd number
return (t * t) % 1000;
}
int main()
{
int m,n;
while(scanf("%d%d",&m,&n) && m)
printf("%d\n",f(m,n));
return 0;
}