分析

首先得明白 。那么我们原式子化为 。卷上一个 之后。 。这里再卷上一个 之后，令 左侧等同于 ，所以 。这个根据积性函数线性筛就好了。要注意 ，可以先把 一起筛出来。

一些符号的使用

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e7 + 1000, P = 998244353;
int qpow(int x,int b) {
    LL a = 1;for(;b;b>>=1,x=1LL*x*x%P)
    if(b&1) a = 1LL * a * x % P;return a;
}
int tot = 0,vis[N];
LL f[N];
int pri[N],n,p,q,id[N],id2[N];
void solve() {
    vis[1] = 1;f[1] = 1;id[1] = 1;
    for(int i = 2;i <= n;i++) {
        if(!vis[i]) {
            pri[++tot] = i;
            id[i] = qpow(i,q) % P;
            if(q >= p)id2[i] = qpow(i,q-p) % P;
            else id2[i] = 1LL * id[i] * qpow(qpow(i,p),P-2) % P;
            f[i] = (1LL * P + 1LL - qpow(id2[i],P-2)) % P;
            f[i] = (1LL * f[i] % P + P) % P;
        }
        for(int j = 1;j <= tot && i * pri[j] <= n;j++)
        {
            vis[pri[j] * i] = 1;
            id[i * pri[j]] = 1LL * id[i] * id[pri[j]] % P;
            id2[i * pri[j]] = 1LL * id2[i] * id2[pri[j]] % P;
            if(!(i%pri[j])) {
                f[i * pri[j]] = f[i];break;
            }
            else {
                f[i * pri[j]] = (1LL *f[i] * f[pri[j]]) % P;
            }
        }
    }
}
int main() {
    cin >> n >> p >> q;
    solve();f[0] = 0;
    for(int i = 1;i <= n;i++) {
        f[i] = (f[i] * id[i]) % P;
        f[i] ^= f[i-1];
    }
    printf("%lld\n",f[n]);return 0;
}