NC23047 - 华华给月月出题

题意

给你一个, 让你求)

数据范围

思路

通过观察发现是积性函数，那么我们可以通过欧拉筛预处理出所有的

和其他预处理不同，因为空间的问题，我们不能再开一个数组来记录，每个数字第一个质因数出现的次数

接着观察可以发现，这个函数也是完全积性函数，那么我们就可以不维护了

代码

/**
 *    author: andif
 *    created: 29.09.2023 19:30:41
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const db eps = 1e-9;
const int mod = 1e9 + 7;
const int N = 13000006;
// int is_p[N], cnt[N], f[N];
int is_p[N], f[N];

int kpow(int a, int b) {
    int ret = 1;
    while(b) {
        if (b & 1) {
            ret = (1ll * ret * a) % mod;
        }
        a = (1ll * a * a) % mod;
        b >>= 1;
    }
    return ret;
}

// int calc_f(int p, int a, int n) {
//     int pa = kpow(p, a);
//     return kpow(pa, n);
// }

void init(int n) {
    vi p;
    p.reserve(10000);
    mt(is_p, 1);
    is_p[1] = 0;
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (is_p[i]) {
            p.eb(i);
            // cnt[i] = 1;
            f[i] = kpow(i, n);
        }
        for (int j = 0; j < sz(p) && i * p[j] <= n; ++j) {
            int k = i * p[j];
            is_p[k] = 0;
            if (i % p[j] == 0) {
                // cnt[k] = cnt[i] + 1;
                int x = i, c = 0;
                while(x % p[j] == 0) c++, x /= p[j];
                int pa = kpow(p[j], c + 1);
                // f[k] = 1ll * f[i] * kpow(calc_f(p[j], cnt[i], n), mod - 2) % mod * calc_f(p[j], cnt[k], n) % mod;
                f[k] = 1ll * f[pa] * f[i * p[j] / pa] % mod;
            }
            f[k] = 1ll * f[i] * f[p[j]] % mod;
            // cnt[k] = 1;
        }
    }
}

int main() {
    qc;
    int n; cin >> n;
    init(n);
    int ans = 0;
    rep(i, 1, n + 1) {
        ans ^= f[i];
    }
    cout << ans << '\n';
    return 0;
}