Bailian4010 2011【循环节】

4010:2011
总时间限制: 1000ms 内存限制: 65536kB
描述
已知长度最大为200位的正整数n，请求出2011^n的后四位。
输入
第一行为一个正整数k，代表有k组数据，k<=200接下来的k行，

每行都有一个正整数n，n的位数<=200
输出
每一个n的结果为一个整数占一行，若不足4位，去除高位多余的0
样例输入
3
5
28
792
样例输出
1051
81
5521

问题链接：Bailian4010 2011
问题简述：（略）
问题分析：大数模幂问题，指数有200位之多，需要找出规律。求的是后4位，那么最多只有10000种，因此余数会构成循环节（根据抽屉原理）。需要先算出循环节再进行计算，不然计算量太大了。打表是需要的。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++语言程序如下：

/* Bailian4010 2011 */

#include <stdio.h>
#include <string.h>

#define N 10000
int ans[N +  1], vis[N + 1], cnt = 0;
char s[200 + 1];

int main(void)
{
    /* 打表找结果后４位的循环节（结果是cnt＝500，即循环节为500） */
    memset(vis, 0, sizeof(vis));
    int a = 2011;
    for(;;) {
        if(vis[a]) break;
        vis[a] = 1;
        ans[cnt++] = a;
        a *= 2011;
        a %= 10000;
    }

    int k, n;
    scanf("%d", &k);
    while(k--) {
        scanf("%s", s);

        int len = strlen(s);
        n = (s[len - 1] - '0');
        if(len >= 2) {
            n += (s[len - 2] - '0') * 10;
            if(len >= 3) n += (s[len - 3] - '0') * 100;
        }
        n--;

        if(n == 0)
            printf("1\n");
        else
            printf("%d\n", ans[n % cnt]);
    }

    return 0;
}