2991:2011 （数学）

【题目描述】

　　　　已知长度最大为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无符号的整数，要转换成有符号）

【代码】

#include <bits/stdc++.h>
using namespace std;
int t,num,ans,b,i;
char a[210];
int main()
{
    scanf("%d",&t);
    while(t--) {
        num=0;
        ans=1;
        b=2011;
        scanf("%s",a);
        for(i=(int)strlen(a)-3;i<(int)strlen(a);i++) if(i>=0) num=num*10+a[i]-'0';
        num%=500;
        for(;num;num>>=1) {
            if(num&1) ans=(long long)ans*b%10000;
            b=(long long)b*b%10000;
        }
        printf("%d
",ans);
    }
}