[luogu 4240] 毒瘤之神的考验

题目背景

Salamander的家门口是一条长长的公路。

又是一年春天将至，Salamander发现路边长出了一排毒瘤！

Salamander想带一些毒瘤回家，但是，这时毒瘤当中钻出来了一个毒瘤之神！

毒瘤之神：你想要带毒瘤走吗？想要带走毒瘤，就必须回答我的问题！如果答不出来的话，你还是乖乖回家吧！

题目描述

毒瘤之神会问T次，每次给定n,m，Salamander需要回答出\(\sum_{i=1}^n\sum_{j=1}^m\varphi(ij)\ mod\ 998244353\)。

Salamander这么辣鸡当然不会做啦，于是把问题丢给了你。

输入输出格式

输入格式：

第一行包含一个正整数T。

接下来T行，每行包含两个正整数，用空格隔开，表示这次询问的n,m。

输出格式：

包含T行每行一个整数表示答案。

输入输出样例

输入样例#1：

输出样例#1：

Solution

神奇的反演题。。

首先有一个比较显然的性质：

\[\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}
\]

证明对于每个质因子考虑就行了。

然后带进去莫比乌斯反演：

\[\begin{align}
ans=&\sum_{i=1}^{n}\sum_{j=1}^m\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\\
=&\sum_{T=1}^{\min(n,m)}\sum_{d|T}\frac{d}{\varphi(d)}\cdot \mu(\frac{T}{d}) \sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\sum_{j=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(jT)
\end{align}
\]

设：

\[f(n)=\sum_{d|n}\frac{d}{\varphi(d)}\cdot \mu(\frac{n}{d})
\]

显然这玩意可以\(O(n\log n)\)预处理出来。

对于后面那个，设：

\[g(n,T)=\sum_{i=1}^{n}\varphi(iT)
\]

然后因为\(n\cdot T\leqslant 1e5\)，所以总共只有\(O(n\log n)\)个值，动态开内存预处理出来就行。

答案变成了：

\[ans=\sum_{t=1}^{\min(n,m)}f(t)g(\lfloor\frac{n}{t}\rfloor,t)g(\lfloor\frac{m}{t}\rfloor,t)
\]

答案是一个数论分块的形式，设：

\[h(n,m,t)=\sum_{i=1}^{t}f(i)g(n,i)g(m,i)
\]

然后我们预处理出\(n,m\leqslant B\)的值，这里先设一个\(B\)出来，现在并不知道他是多少。

然后分析下复杂度，此时\(ans\)里的\(T\geqslant n/B\)，所以对于\(T \leqslant n/B\)的直接暴力来算出就好了，剩下的数论分块之后利用\(h\)减一下就好了。

时间复杂度为\(O(n\log n+B^2n+T(\sqrt{n}+\lfloor\frac{n}{B}\rfloor))\)。

取最小值即\(B^2n=T\cdot \frac{n}{B}\)，解得\(B=\sqrt[3]{T}\thickapprox 30\)。

#include<bits/stdc++.h>

using namespace std;

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

void print(int x) {

    if(x<0) putchar('-'),x=-x;

    if(!x) return ;print(x/10),putchar(x%10+48);

}

void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define pb push_back

const int maxn = 1e5+10;

const int B = 30;

const int mod = 998244353;

int pri[maxn],mu[maxn],vis[maxn],tot,f[maxn],phi[maxn],inv[maxn];

vector <int > g[maxn],h[B+1][B+1];

void prepare(int n) {

    mu[1]=inv[1]=phi[1]=1;

    for(int i=2;i<=n;i++) {

        if(!vis[i]) mu[i]=-1,pri[++tot]=i,phi[i]=i-1;

        for(int j=1;j<=tot&&i*pri[j]<=n;j++) {

            vis[i*pri[j]]=1;

            if(i%pri[j]==0) {phi[i*pri[j]]=phi[i]*pri[j];break;}

            mu[i*pri[j]]=-mu[i];

            phi[i*pri[j]]=phi[i]*(pri[j]-1);

        }

        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

    }

    for(int d=1;d<=n;d++)

        for(int T=d;T<=n;T+=d)

            f[T]=(f[T]+1ll*d*inv[phi[d]]%mod*mu[T/d])%mod;

    for(int i=0;i<=n;i++) g[0].pb(0);

    for(int i=1;i<=n;i++) {

        int l=(n/i);g[i].pb(0);

        for(int j=1;j<=l;j++)

            g[i].pb((g[i-1][j]+phi[i*j])%mod);

    }

    for(int i=1;i<=B;i++)

        for(int j=1;j<=B;j++) {

            int l=min(n/i,n/j);h[i][j].pb(0);

            for(int k=1;k<=l;k++)

                h[i][j].pb((h[i][j][k-1]+1ll*f[k]*g[i][k]%mod*g[j][k]%mod)%mod);

        }

}

void solve() {

    int n,m;read(n),read(m);if(n>m) swap(n,m);

    int ans=0;

    for(int i=1;i<=m/B;i++) ans=(ans+1ll*f[i]*g[n/i][i]%mod*g[m/i][i]%mod)%mod;

    int T=m/B+1;

    while(T<=n) {

        int pre=T;T=min(n/(n/T),m/(m/T));

        ans=(1ll*(ans+h[n/T][m/T][T])-h[n/T][m/T][pre-1])%mod;T++;

    }write((ans+mod)%mod);

}

int main() {

    prepare(100000);

    int t;read(t);

    while(t--) solve();

    return 0;

}

巴特西