一本通-1234：2011（基础分治，易错）

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

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

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

【输入样例】 3 5 28 792

【输出样例】 1051 81 5521

---

最开始写了个暴力的解法，超时了，模拟了高精度。

#include <bits/stdc++.h>

using namespace std;

const int MODE = 10000;

inline bool notZero(const string & s)
{
    if (s.size() > 1) return true;

    return s[0] - '0' != 0;
}

inline bool isOdd(const string & s)
{
    int n = s.size();
    return (s[n - 1] - '0') & 1;
}

string myToString(int n)
{
    string res;
    while (n) {
        res.push_back('0' + n % 10);
        n /= 10;
    }
    reverse(res.begin(), res.end());

    return res;
}

void divide(string & s, int num)
{
    string res;
    int n = s.size();
    int extra = 0;
    for (int i = 0; i < n; ++i) {
        int tmp = extra * 10 + (s[i] - '0');
        // res += to_string(tmp / num);
        res += myToString(tmp / num);
        extra = tmp % num;
    }
    int pos = 0;
    while (pos < (int)res.size() - 1) {
        if (res[pos] == '0') ++pos;
        else break;
    }
    s = res.substr(pos);
}


int solve(int base, string s)
{
    int res = 1;
    while (notZero(s)) {
        if (isOdd(s)) res = res * base % MODE;
        base = base * base % MODE;
        divide(s, 2);
    }

    return res;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;
    while (caseNum--) {
        string n; cin >> n;
        cout << solve(2011, n) << endl;
    }

    return 0;
}

然后发现只取后四位，在一定指数大小下会出现循环，所以先找出这个循环。

#include <bits/stdc++.h>

using namespace std;

const int MODE = 10000;

int num = 2011;

int solve()
{
    int res = 2011;
    int cnt = 1;
    while (true) {
        res = res * 2011 % MODE;
        ++cnt;
        if (res == num) break;
    }

    return cnt;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cout << solve() << endl;

    return 0;
}

这个结果得出是501，那么意味着每$2011^{500}$就会出现一次循环。也就是指数为1001，15001的时候后四位都是2011，所以无论给出的指数多大，都只需要取后三位就可以了。

#include <bits/stdc++.h>

using namespace std;

const int MODE = 10000;

int getNum(const string & s)
{
    int res = 0;
    int n = s.size();
    if (n <= 3) {
        for (int i = 0; i < n; ++i) {
            res = res * 10 + s[i] - '0';
        }

        return res;
    }

    return getNum(s.substr(n - 3));
}

int solve(string & s)
{
    int n = getNum(s);
    n %= 500;
    if (n == 0) n = 500;

    int res = 1, base = 2011;
    while (n) {
        if (n & 1) res = res * base % MODE;
        base = base * base % MODE;
        n >>= 1;
    }

    return res;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;
    while (caseNum--) {
        string number; cin >> number;
        cout << solve(number) << endl;
    }

    return 0;
}