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$ 预处理出来了。 再运用前缀和和数论分块，此题完结。 ## 代码 ```cpp #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; } ```