C++ string赋值空串未生效 数字整除编程题代码错误求解

核心问题说明 #

number = ""本身是可以正常清空字符串的，你误以为清空失败的根本原因是每次测试用例结束后没有清空digits数组，下一轮测试用例的数字位会追加到上一轮的digits后面，导致拼接的number永远包含之前测试用例的内容，看起来就像没清空一样。

除此之外你的代码还存在多个不符合题目约束的致命逻辑错误：

• 题目中N可以达到1e18，你写的循环for (int i = 2; i <= (n - 1); i++)完全无法运行，1e18次循环会直接超时，且digits数组根本存不下这么多元素。
• 你把所有位拼接成字符串后用stoi转整数，int最大只能保存约10位的十进制数，只要N>10就会直接溢出，得到的数值完全错误，更别说N到1e18的场景。
• 不需要拼接整个大整数再取模，利用模运算性质(a * 10 + b) % mod = [(a % mod) * 10 + b] % mod就可以边计算位边算模，效率极高。

正确实现思路 #

因为Q<10，递推式Pi = (4*Pi-1 + Pi-2) % Q的状态由(Pi-1, Pi)决定，最多只有Q*Q=81种状态，必然存在循环节，就算N是1e18也可以快速计算：

1. 特判N=1的情况：直接返回P0 % Q == 0的结果
2. N>=2的时候，初始化余数为(P0 * 10 + P1) % Q
3. 递推后续的位，每得到一位Pi就更新余数：余数 = (余数 * 10 + Pi) % Q
4. 找到循环节后直接跳过重复的循环部分，不用遍历到N

修正后的代码 #

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 关闭cin同步提升输入速度，适配1e5测试用例
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        long long n;
        int p0, p1, q;
        cin >> p0 >> p1 >> q >> n;
        if (n == 1) {
            cout << (p0 % q == 0 ? "YES\n" : "NO\n");
            continue;
        }
        if (n == 2) {
            int val = (p0 * 10 + p1) % q;
            cout << (val == 0 ? "YES\n" : "NO\n");
            continue;
        }
        long long rem = (p0 * 10LL + p1) % q;
        int a = p0, b = p1;
        long long left = n - 2;
        vector<pair<int, int>> state;
        vector<long long> rem_list;
        while (left > 0) {
            int c = (4 * b + a) % q;
            rem = (rem * 10LL + c) % q;
            a = b;
            b = c;
            left--;
            // 查找循环节
            auto cur = make_pair(a, b);
            bool found = false;
            for (int i = 0; i < state.size(); i++) {
                if (state[i] == cur) {
                    long long cycle_len = state.size() - i;
                    long long skip = left / cycle_len;
                    left = left % cycle_len;
                    found = true;
                    break;
                }
            }
            if (!found) {
                state.push_back(cur);
                rem_list.push_back(rem);
            }
        }
        cout << (rem % q == 0 ? "YES\n" : "NO\n");
    }
    return 0;
}

性能说明 #

因为Q最大是9，所以状态最多只有81种，每个测试用例最多遍历81次就能找到循环节，就算T是1e5，总运算量也只有8.1e6，完全符合时间要求。

内容的提问来源于stack exchange，提问作者WildHuman