题解：P12599 常数要较小

· · 题解

题目传送门。

典。不明白 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;
}