信息学奥赛一本通 1234：2011（evd）

【题目描述】
已知长度最大为200位的正整数n，请求出2011n的后四位。

【输入】
第一行为一个正整数k，代表有k组数据（k≤200），接下来的k行，每行都有一个正整数n，n的位数≤200。

【输出】
每一个n的结果为一个整数占一行，若不足4位，去除高位多余的0。

【输入样例】
3
5
28
792
【输出样例】
1051
81
5521
【心得】需要数学知识的帮助，正整数的n次幂的后几位是循环的。2011的后四位的循环周期是500，所以只需要算后三为就可以了，剩下的就分治吧！
【AC代码】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
const int M=10000;
const int C=2011;
using namespace std;
int main()
{
    int n,i,len,m,x;char str[205];cin>>n;while(n--){
    cin>>str;len=strlen(str);m=0;for(i=max(0,len-4);i<=len-1;i++) m=10*m+str[i]-'0';i=1;x=C;while(i*2<=m){
    x=(x*x)%M;i*=2;}for(i=i+1;i<=m;i++) x=(x*C)%M;cout<<x<<endl;}return 0;
}