洛谷 5495 Dirichlet 前缀和 (模板)

题目：传送门

复杂度 O(NloglogN)

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF 0x3f3f3f3f
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x) & (-(x)))
using namespace std;

UI seed;

const int N = 2e7 + 5;

const int M = 2e6 + 5;

bool vis[N];

UI a[N];

int pre[M], tot, n;

int get() {

    seed ^= seed << 13;

    seed ^= seed >> 17;

    seed ^= seed << 5;

    return seed;

}

int main() {

    cin >> n >> seed;

    rep(i, 1, n) a[i] = get();

    rep(i, 2, n) {

        if(!vis[i]) pre[++tot] = i;

        rep(j, 1, tot) {

            if(i * pre[j] > n) break;

            vis[i * pre[j]] = 1;

            if(i % pre[j] == 0) break;

        }

    }

    rep(i, 1, tot) {

        rep(j, 2, n) {

            if(pre[i] * j > n) break;

            a[pre[i] * j] += a[j];

        }

    }

    UI ans = a[1];

    rep(i, 2, n) ans ^= (a[i] + a[1]);

    cout << ans << endl;

    return 0;

}