2991:2011

总时间限制: 

1000ms

内存限制: 

65536kB

描述

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

输入

第一行为一个正整数k，代表有k组数据，k<=200接下来的k行，

每行都有一个正整数n，n的位数<=200

输出

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

样例输入

3528792

样例输出

1051815521

思路：

2011的n次方，这个n很大，小于等于200位，一看就是字符串读入，因为只取最后四位，这时候要推测出题者用意，2011的次方后四位是否会出现一个循环节。

想起2016年湘潭赛那个2016，也是快速乘法，发现有循环节之后更加好做。

这里一样。预处理打表，注释部分，打出i的出现相同的a[i]下标，发现1 501 1001 1501。所以循环节是500.

因为只留最后4位，所以每次打表的时候取模10000，留下最后四位就好。

因为500一循环，只要最大三位数即可，没有三位的直接转换。

注意n的位数，一开始只开了25，发生玄学问题。。。。(25放全局可以过，250放局部可以过，RE)

#include 
     
      using namespace std;const int maxn = 10000+5;int a[maxn] = {
   0,2011};void pre(){    for(int i = 2; i <= 10000; i++)    {        a[i] = (a[i-1]*2011)%10000;    }}int main(){          pre();//   for(int i = 1; i <= 10000; i++) {//    if(a[i]==2011) {//        cout<
      <
       
        =3)        {//        for(int i = len-1,j = 0; i >= len-3; i--,j++) {//            cout<<(pow(10,j))<