牛客练习赛69 F 解方程

迪利克雷卷积的性质告诉我们，积性函数卷积性函数的得到的结果也是积性函数。
题目公式中有两个积性函数，因此可以推断出f也是一个积性函数。
因此我们只要处理出所有f(p^k) (p是质数)的值即可线性筛，复杂度O(n)。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

const int N = 1e7 + 100;
const int MOD = 998244353;

ll qpow(ll x, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % MOD;
        n /= 2;
        x = x * x % MOD;
    }
    return res;
}

int n, p, q;
int pri[N / 10], fu[N], tot;
int fp[N], fq[N], f[N];
bool is_pri[N];

void init() {
    memset(is_pri, true, sizeof(is_pri));
    fu[1] = fp[1] = fq[1] = f[1] = 1;
    for (int i = 2; i < N; i++) {
        if (is_pri[i]) {
            pri[tot++] = i;
            fu[i] = i;
            fp[i] = qpow(i, p);
            fq[i] = qpow(i, q);
            f[i] = fq[i] - fp[i];
            if (f[i] < 0) f[i] += MOD;
            ll sum = f[i] + fp[i];
            if (sum >= MOD) sum -= MOD;
            for (ll j = 1LL * i * i; j < N; j *= i) {
                fp[j] = (1LL * fp[j / i] * fp[i]) % MOD;
                fq[j] = (1LL * fq[j / i] * fq[i]) % MOD;
                f[j] = (fq[j] - sum * fp[i]) % MOD;
                if (f[j] < 0) f[j] += MOD;
                sum = (sum * fp[i] + f[j]) % MOD;
            }
        }
        for (int j = 0; i * pri[j] < N; j++) {
            int t = i * pri[j];
            is_pri[t] = false;
            if (i % pri[j] == 0) {
                fu[t] = fu[i] * pri[j];
                f[t] = 1LL * f[t / fu[t]] * f[fu[t]] % MOD;
                break;
            }
            else {
                fu[t] = pri[j];
                f[t] = 1LL * f[t / fu[t]] * f[fu[t]] % MOD;
            }
        }
    }
}

int main() {
    //freopen("0.txt", "r", stdin);
    scanf("%d%d%d", &n, &p, &q);
    init();
    int ans = 0;
    for (int i = 1; i <= n; i++) ans ^= f[i];
    printf("%d\n", ans);
    return 0;
}