题解 | many sum

首先，数组 A 的递推是线性的，可以直接递推出来。然后考虑数组 B，直接枚举 i 的约数不容易，但是枚举 i 的倍数却很简单，所以我们考虑处理每个 A[i] 带给 B[j] () 的贡献。

1. 从 1 到 n 枚举 i
2. 从 i 到 n 枚举 j，每次递进 i。
3. B[j] += A[i]

处理完后，直接求答案即可。由调和级数证明该做法为 。

如果 的大小是 的话，可以考虑线性筛求出倍数，枚举质数 i 和质数的倍数 j 执行 B[j] += A[i]。由 Mertens 第二定理知道这么做的时间复杂度为 ，计算量大概为 ，可以通过。

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

using i64 = long long;

const int N = 2e6 + 10;

int n, a[N], mod;
i64 b[N];

inline void solve() {
    cin >> n >> a[1] >> mod;
    for (int i = 1; i <= n; i++) {
        if (i > 1) a[i] = (a[i - 1] + 7 * i) % mod;
        for (int j = i; j <= n; j += i)
            b[j] += a[i];
    }
    i64 ans = 0;
    for (int i = 1; i <= n; i++)
        ans ^= b[i];
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false); 
    cin.tie(nullptr); 

    int t = 1; 
    // cin >> t;

    while (t--) {
        solve();
    }
    return 0;
}
/*

*/