自动搬运

查看原文

来自洛谷，原作者为

	Polarisx 一位努力不落后的 NPC

搬运于2025-08-24 23:16:43，当前版本为作者最后更新于2025-05-24 16:13:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门。

典。不明白 $T\le 10^4$ 的意义。

思路

以下除法默认整除。

$$\begin{aligned} \sum_{i=1}^n \sum_{j=1}^n \mu(ij)ij &= \sum_{i=1}^n \sum_{j=1}^n \mu(i)\mu(j)[\gcd(i,j)=1]ij\\ &=\sum_{d=1}^n \mu(d)d^2\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}ij\mu(id)\mu(jd)\\ &=\sum_{d=1}^n \mu(d) d^2\left( \sum_{i=1}^{n/d}i\mu(id) \right)^2 \end{aligned} $$

一般人看到这种式子就直接上数论分块了，事实上这个式子是可以预处理的。

考虑 $n\to n+1$，式子的哪些部分改变了，首先就是后面括号内的式子，当且仅当 $d\mid n+1$ 时才会有 $n/d+1=(n+1)/d$，不妨枚举 $d\mid n+1$，计算变化量就行了，最后不要忘了加上 $d=n+1$ 时的贡献。

时间复杂度 $\mathcal O(n\ln n+q)$。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Mod=998244353;
const int Maxn=1e6+7;
int T,n;
int mu[Maxn];
vector<int>divs[Maxn];
int ans[Maxn];
int f[Maxn];

void init(int N){
    for(int i=1;i<=N;i++){
        mu[i]+=(i==1);
        for(int j=i+i;j<=N;j+=i) mu[j]-=mu[i],divs[j].emplace_back(i);
    }
    
    for(int i=1;i<=N;i++){
        ans[i]=ans[i-1];
        for(auto j:divs[i]){
            int w=mu[j]*1ll*j*j%Mod;
            int delt=((i/j)*mu[i]+f[j])%Mod;
            int val=(1ll*delt*delt-1ll*f[j]*f[j])%Mod;
            ans[i]=(ans[i]+1ll*w*val)%Mod;
            f[j]=delt;
        }
        f[i]=mu[i];
        ans[i]=(ans[i]+abs(f[i])*mu[i]*1ll*i*i)%Mod;
    }

}

int main(){
    scanf("%d",&T);
    init(1e6);
    while(T--){
        scanf("%d",&n);
        ans[n]=(ans[n]%Mod+Mod)%Mod;
        printf("%d\n",ans[n]);
    }

    system("pause");
    return 0;
}