【题目描述】

　　　　已知长度最大为200位的正整数n，请求出2011^n的后四位。

【题目链接】

　　　　http://noi.openjudge.cn/ch0204/2991/

【算法】

　　　　一开始想的是把n转换成二进制，然后快速幂，但要用到高精度除法，很烦。容易发现2011的501次方mod10000后为2011，所以2011的n次方和2011的n%500次方膜10000同余，而n%500和n的后三位的数%500结果应该相同，然后快速幂结束。（注意：strlen（）返回值是size_t无符号的整数，要转换成有符号）

【代码】

1 #include 
     
       2 using namespace std; 3 int t,num,ans,b,i; 4 char a[210]; 5 int main() 6 { 7     scanf("%d",&t); 8     while(t--) { 9         num=0;10         ans=1;11         b=2011;12         scanf("%s",a);13         for(i=(int)strlen(a)-3;i<(int)strlen(a);i++) if(i>=0) num=num*10+a[i]-'0';14         num%=500;15         for(;num;num>>=1) {16             if(num&1) ans=(long long)ans*b%10000;17             b=(long long)b*b%10000;18         }19         printf("%d\n",ans);20     }21 }