题解 | #many sum#

计算即可，但需要注意，如果直接枚举计算，将会是的复杂度，我们需要跳过一些不必要的计算：如果对有贡献，那么对都有贡献，因此可以从枚举，计算对哪些项有贡献。

事实上，形如以下的(比如说大运算符换成求积)，若需要求整个，都可以这么算，可以证明总时间复杂度为.

时间复杂度的证明并不困难，这里仅粗略解释一下：

由于跳过了不整除的， 事实上求的工作量为，因此求和得到

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

int main() {
    int n,a1,m;
    cin >> n >> a1 >> m;
    vector<int> a(n+1,0);
    a[1]=a1;
    for(int i=2;i<=n;i++) a[i]=(a[i-1]+7*i)%m;

    vector<int> b(n+1,0);
    
    for(int d=1;d<=n;d++){
        for(int i=d;i<=n;i+=d){
            b[i]+=a[d];
        }
    }
    int ans = 0;
    for(auto num : b) ans^=num;
    cout << ans;

}