当前位置：首页 > news >正文

规律打表，找循环节，类似2016湘潭那个2016

news 来源：原创 2024/5/3 11:11:17

2991:2011

查看
提交
统计
提问

总时间限制:

1000ms

内存限制:

65536kB

描述

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

输入

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

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

输出

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

样例输入

样例输出

1051
81
5521

思路：

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

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

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

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

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

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

#include <bits/stdc++.h>

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<<i<<endl;
//    }
//   }
    int T;
    scanf("%d",&T);
    while(T--)
    {      
        char str[250];
        int n = 0;
        scanf("%s",str);
        int len = strlen(str);
        if(len>=3)
        {
//        for(int i = len-1,j = 0; i >= len-3; i--,j++) {
//            cout<<(pow(10,j))<<endl;
//            n += (str[i]-'0')*(pow(10,j));
//            }
            for(int i = len-3; i <= len - 1; i++)
            {
                n = n*10 + str[i]-'0';
            }
        }
        else
        {
            n = atoi(str);
        }
        n %= 500;
        printf("%d\n",a[n]);
    }
    return 0;
}