1234：2011——快速幂+高精除

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

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

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

【输入样例】
3
5
28
792
【输出样例】
1051
81
5521

分析

解法一 快速幂+高精除

1. 刚开始没看清题，以为n<=200，就直接for循环暴力求2011的n次幂，后来提交发现TLE，以为暴力for太慢了，然后用快速幂，发现WA了，后来知道n的位数是小于200，所以直接爆int、long long了；所以此处需要用到高精度运算，用数组去存储n的每一位；
2. 这里我用了一个len表示n数组的有效长度，也可以用n[0]来存数组长度（n的有效值长度），在改变数组的函数中(change函数、divide函数中)，改变完重新给n[0]赋值。
3. 将原来快速幂的幂用数组表示，有这些操作：判断n是否为0，以及n/2，以及n的最后一位是否为1，用数组模拟即可；
4. 高精度除一个小的数，还是比较简单的，没那么复杂；
   

#include<bits/stdc++.h>using namespace std;int k, ans;
int len;//表示n数组的有效长度，也可以用a[0]来存数组长度，在改变数组的函数中(change函数、数组除以2的函数中)，改变完重新给a[0]赋值
string s;
int n[205];//把n数组表示的数除2
void divide() {int x = 0;//表示上一位的余数for (int i = len - 1; i >= 0; i--) {x = x * 10 + n[i];n[i] = x / 2;x = x % 2;//当前的余数}//去除前导0，比如02352while (n[len - 1] == 0 && len > 1) {len--;}
}//指数为高精度数字的数组n的快速幂
int quickPower(int a) {int res = 1;int temp = a;while (len > 1 || (len == 1 && n[len - 1] != 0)) {//n不为0if (n[0] % 2) {res = res * temp % 10000;}//b = b >> 1;换为高精除divide();temp = temp * temp % 10000;}return res;
}//把s存在n数组中
void change(string s) {len = s.size();for (int i = 0; i < len; i++)n[i] = (s[len - i - 1] - '0');
}int main() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cin >> k;while (k--) {memset(n, 0, sizeof n);cin >> s;//注意n是200位的数字，远大于long longchange(s);//超时，以为n是范围小于200的数/*for (int i = 1; i <= n; i++) {ans = ans * 2011 % 10000;}*/ans = quickPower(2011);cout << ans << endl;}return 0;
}

解法二 利用2011^500 % 10000=1

参考的：信息学奥赛一本通 1234：2011 | OpenJudge NOI 2.4 2991:2011

1. 循环长度：假如求后k位值，如果n的循环长度是L，那么说明对于任意的正整数a，n ^ a = n ^ (a+L)的最后k位都相同。看a的几次方模10000的结果等于a，就能找出循环长度。
2. 由于2011^500 % 10000=1，所以2011 ^ 1 = 2011 ^ 501（指的后4位的值相等） ，所以此题的循环长度为500；也就是 a ^ b % 10000 = a ^ (b+500) % 10000；
3. 所以指数n只取三位即可求得结果，然后直接暴力for就能算，就不用上面的高精除+快速幂；
4. 本题通过了一个f函数求得，2011 ^ 501 % 10000 = 2011 ^ 1 % 10000，故循环长度就是500；

#include<bits/stdc++.h>using namespace std;int k, ans;
string s;//看a的几次方模10000的结果等于a，来找循环长度
int f(int a) {int i = 1, temp = a;while (++i) {temp = temp * a % 10000;if (temp == a)break;}return i;
}int main() {std::ios::sync_with_stdio(false);cin.tie(nullptr);//找循环长度
//    int len = f(2011);
//    cout << len;      =>len=501cin >> k;while (k--) {cin >> s;int b = 0;//保留后三位指数即可if (s.size() >= 3) {//指数长度超过3位，取最后3位for (int i = s.size() - 3; i < s.size(); i++) {b = b * 10 + s[i] - '0';}} else {//不足3位，有几位取几位for (int i = 0; i < s.size(); i++)b = b * 10 + s[i] - '0';}b %= 500;//循环长度为500ans = 1;for (int i = 1; i <= b; i++) {ans = ans * 2011 % 10000;}cout << ans << endl;}return 0;
}