题解 | #many sum#_牛客博客

埃氏筛法

根据题意序列 $B_i=\sum_{d|i}^{} A_d$ 表示 $B_i$ 是 $A_i$ 的所有因子项的和，即

B_6 = A_1+A_2+A_3+A_6

对于每一个数如果简单判断因子，其复杂度会达到 $O(N\sqrt{N})$ 导致超时。那么我们考虑使用筛法：对于每一个下标 $k$ （ $1 \leqslant k \leqslant N$ ），以及所有满足 $1 \leqslant nk \leqslant N$ 的整数 $n$ ，我们将 $A_k$ 的值累加到 $B_{nk}$ 上。这样，总的操作次数约为 $\sum_{k=1}^{N} \lfloor N/k \rfloor$ 。

由于调和级数的性质， $\sum_{k=1}^{N} \frac{1}{k} \sim \ln N + \gamma$ （其中 $\gamma$ 为欧拉常数，当 $N \to +\infty$ 时），因此总操作次数约为 $N \sum_{k=1}^{N} \frac{1}{k} \sim N \ln N$ 。故算法的时间复杂度为 $O(N \log N)$ 。

AC Code

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

int main()
{
    int n, a1, m;
    cin >> n >> a1 >> m;
    vector<int> ai(n + 1), bi(n + 1);
    ai[1] = a1;
    for (int i = 2; i <= n; i++)
    {
        ai[i] = (ai[i - 1] + 7 * i) % m;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j += i)
        {
            bi[j] += ai[i];
        }
    }
    int xors = bi[1];
    for (int i = 2; i <= n; i++)
    {
        xors ^= bi[i];
    }
    cout << xors;
    return 0;
}