P12599

· · 题解

题解

你好。

莫比乌斯函数为积性函数，因此有 \mu(ij) = \mu(i)\mu(j) 当且仅当 \gcd(i,j)=1 时成立。

所以这个式子可以化为

\sum_{i=1}^{n}\sum_{j=1}^{n} \mu(i)\mu(j)ij[\gcd(i,j)=1]

然后因为 \varepsilon(x)=\sum_{d \mid x} \mu(x)，\varepsilon(1)=1，所以这个式子又变了。

\sum_{i=1}^{n}\sum_{j=1}^{n}\mu(i)\mu(j)ij \sum_{d \mid i,d \mid j} \mu(d)

然后因为 d \mid i,d \mid j，因此设 i=dx,j=dy，转化得

&=\sum_{d=1}^{n}\mu(d)\sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor} xd \cdot \mu(xd) \sum_{y=1}^{\lfloor{\frac{n}{d}}\rfloor} yd \cdot \mu(yd) \end{aligned}

注意到出现了两个形式上一样的式子，直接合并。

=\sum_{d=1}^{n}\mu(d)(\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor} id \cdot \mu(id))^{2}

设 f(x,y)=\sum_{i=1}^{y} xi \cdot \mu(xi)。

所以

=\sum_{d=1}^{n}\mu(d)f^{2}(d,\lfloor\frac{n}{d}\rfloor)

发现 f(x,y)=f(x,y-1)+xy \cdot \mu(xy)。

然后就可以把 f 预处理出来了。

再运用前缀和和数论分块，此题完结。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6;
const ll p=998244353;
int t,n;
int mu[N+2],prime[N+2],cnt;
ll ans;
bool isp[N+2];
vector<ll> f[N+2],sum[N+2];
int main() {
    mu[1]=1;
    for(int i=2;i<=N;i++) {
        if(!isp[i]) prime[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++) {
            isp[i*prime[j]]=1;
            if(i%prime[j]==0) break;
            mu[i*prime[j]]=-mu[i];
        }
    }
    f[0].resize(N);
    for(int i=1;i<=N;i++) {
        f[i].resize(N/i+2);
        for(int j=1;j<=N/i;j++) f[i][j]=(f[i-1][j]+mu[i*j]*i*j%p)%p;
    }
    for(int i=1;i<=N;i++) {
        sum[i].resize(N/i+2);
        for(int j=1;j<=N/i;j++) sum[i][j]=(sum[i][j-1]+mu[j]*f[i][j]*f[i][j]%p)%p;
    }
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        ans=0ll;
        for(int l=1,r;l<=n;l=r+1) {
            r=n/(n/l);
            ans=(ans+sum[n/l][r]-sum[n/l][l-1])%p;
        }
        printf("%lld\n",(ans+p)%p);
    }
    return 0;
}