大数求和

题意解析

对于题目中的式子，我们有 $\sum_{k=1}^{N}k \mod M = N \times (N + 1) / 2 \mod M$。

但是由于本题的 $N (1 \le N \le 10^{4 \times 10^6})$ 非常大，直接计算上面的式子时间复杂度为 $\mathrm{\mathrm{O}}(\log^2{N})$，计算量大概为 $1.6 \times 10^{13}$，会超出时间限制。

我们考虑 $1 + 2 + 3 + \cdots + 2 \times M - 1 + 2 \times M = M \times (2 \times M + 1)$。

而 $M \times (2 \times M + 1) \vert M$，即每 $2 \times M$ 个数字的和对 $M$ 取余的值为 $0$。

令 $K = N \mod (M \times 2)$，我们只需要计算最后的 $K$ 个数字的和即可。

而最后的 $K$ 个数字的形式为 $i \times M \times 2 + 1, i \times M \times 2 + 2, i \times M \times 2 + 3, \cdots + i \times M \times 2 + K$。

每个数字对 $M$ 取余得到 $1 + 2 + 3 + \cdots + K = K \times (K + 1) / 2$。

对于本题 $M(1 \le M \le 10^9), K(0 \le K < M \times 2)$，可以直接做整形运算。

对于 $N$，令其长度为 $n$， 我们可以将其写成 $\sum_{i=0}^{n}a[i] \times 10^i$，其中 $a[i]$ 为其从低位到高位上的数字。那么我们便可以从逐位处理求得 $N \mod (M \times 2)$。

AC代码

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        string s; cin >> s;
        int m; cin >> m;
        i64 res = 0;
        for (auto &ch : s) {
            res = res * 10 + ch - '0';
            res %= m * 2;
        }
        res = (res + 1) * res / 2 % m;
        cout << res << '\n';
    }
    return 0;
}

复杂度分析

求 $N \mod (M \times 2)$ 的时间复杂度为 $\mathrm{O}(\log{N})$；
计算 $K \times (K + 1) / 2 \mod M$。的时间复杂度为 $\mathrm{O}(1)$。