P4240 毒瘤之神的考验【莫比乌斯反演+各种数学技巧】

毒瘤题

题意：

$T$T 次询问，每次给定 $n,m$n,m ，求： $\left({\sum }_{i=1}^n{\sum }_{j=1}^m\phi \left(ij\right)\right)\hspace{0.25em} mod\hspace{0.25em} 998244353$(∑i=1n​∑j=1m​φ(ij))mod998244353 的值。

数据范围： $1\le T\le 10^4,1\le n,m\le 10^5$1≤T≤104,1≤n,m≤105

解题过程：

以下过程中 $n=min(n,m)$n=min(n,m)；
首先要知道如下性质：

$\phi \left(ab\right)=\frac{\phi \left(a\right)\phi \left(b\right)\ast gcd(a,b)}{\phi \left(gcd\right(a,b\left)\right)}$φ(ab)=φ(gcd(a,b))φ(a)φ(b)∗gcd(a,b)​

证明：

$\phi \left(a\right)\phi \left(b\right)=a\prod _{p\mid a}\frac{p-1}{p}\hspace{0.25em} b\prod _{p\mid b}\frac{p-1}{p}$φ(a)φ(b)=ap∣a∏​pp−1​bp∣b∏​pp−1​
$=ab\prod _{p\mid ab}\frac{p-1}{p}\prod _{p\mid gcd(a,b)}\frac{p-1}{p}$=abp∣ab∏​pp−1​p∣gcd(a,b)∏​pp−1​
两边同时乘以 $gcd(a,b)$gcd(a,b)，有：
$\phi \left(a\right)\hspace{0.25em} \phi \left(b\right)\hspace{0.25em} gcd(a,b)=\phi \left(ab\right)\hspace{0.25em} \phi \left(gcd\right(ab\left)\right)$φ(a)φ(b)gcd(a,b)=φ(ab)φ(gcd(ab))
即证。

接下来就可以进行神奇的化简过程：

$\sum _{i=1}^n\sum _{j=1}^m\phi \left(ij\right)$i=1∑n​j=1∑m​φ(ij)
$=\sum _{i=1}^n\sum _{j=1}^m\phi \left(i\right)\phi \left(j\right)\frac{gcd(i,j)}{\phi \left(gcd\right(i,j\left)\right)}$=i=1∑n​j=1∑m​φ(i)φ(j)φ(gcd(i,j))gcd(i,j)​
$=\sum _{d=1}^n\sum _{i=1}^n\sum _{j=1}^m\phi \left(i\right)\phi \left(j\right)\frac{d}{\phi \left(d\right)}\left[gcd\right(i,j)=d]\hspace{0.25em} \left(改变枚举顺序\right)$=d=1∑n​i=1∑n​j=1∑m​φ(i)φ(j)φ(d)d​[gcd(i,j)=d](改变枚举顺序)
$=\sum _{d=1}^n\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }\phi \left(id\right)\phi \left(jd\right)\frac{d}{\phi \left(d\right)}\left[gcd\right(i,j)=1]$=d=1∑n​i=1∑⌊dn​⌋​j=1∑⌊dm​⌋​φ(id)φ(jd)φ(d)d​[gcd(i,j)=1]
$=\sum _{d=1}^n\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }\phi \left(id\right)\phi \left(jd\right)\frac{d}{\phi \left(d\right)}\sum _{k\mid gcd(i,j)}\mu \left(k\right)$=d=1∑n​i=1∑⌊dn​⌋​j=1∑⌊dm​⌋​φ(id)φ(jd)φ(d)d​k∣gcd(i,j)∑​μ(k)
$=\sum _{d=1}^n\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }\phi \left(id\right)\phi \left(jd\right)\frac{d}{\phi \left(d\right)}\sum _{k\mid i,k\mid j}\mu \left(k\right)$=d=1∑n​i=1∑⌊dn​⌋​j=1∑⌊dm​⌋​φ(id)φ(jd)φ(d)d​k∣i,k∣j∑​μ(k)
$=\sum _{d=1}^n\frac{d}{\phi \left(d\right)}\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }\phi \left(id\right)\phi \left(jd\right)\sum _{k\mid i,k\mid j}\mu \left(k\right)$=d=1∑n​φ(d)d​i=1∑⌊dn​⌋​j=1∑⌊dm​⌋​φ(id)φ(jd)k∣i,k∣j∑​μ(k)
$=\sum _{d=1}^n\frac{d}{\phi \left(d\right)}\sum _{k=1}^{\lfloor \frac{n}{d}\rfloor }\mu \left(k\right)\sum _{i=1}^{\lfloor \frac{n}{dk}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{dk}\rfloor }\phi \left(idk\right)\phi \left(jdk\right)$=d=1∑n​φ(d)d​k=1∑⌊dn​⌋​μ(k)i=1∑⌊dkn​⌋​j=1∑⌊dkm​⌋​φ(idk)φ(jdk)
令 $T=dk$T=dk,
$=\sum _{T=1}^n\sum _{k\mid T}\frac{k}{\phi \left(k\right)}\mu \left(\frac{T}{k}\right)\sum _{i=1}^{\lfloor \frac{n}{T}\rfloor }\phi \left(iT\right)\sum _{j=1}^{\lfloor \frac{m}{T}\rfloor }\phi \left(jT\right)$=T=1∑n​k∣T∑​φ(k)k​μ(kT​)i=1∑⌊Tn​⌋​φ(iT)j=1∑⌊Tm​⌋​φ(jT)
令 $F\left(x\right)={\sum }_{k\mid x}\frac{k}{\phi \left(k\right)}\mu \left(\frac{x}{k}\right)\hspace{0.25em}$F(x)=∑k∣x​φ(k)k​μ(kx​), 显然可以通过先枚举因子再枚举倍数的方法（即埃氏筛的原理）在 $O\left(nlogn\right)$O(nlogn) 的时间内预处理出来。

令 $G\left[x\right]\left[y\right]={\sum }_{i=1}^y\phi \left(ix\right)$G[x][y]=∑i=1y​φ(ix) ，显然有 $G\left[x\right]\left[y\right]=G\left[x\right][y-1]+\phi \left(yx\right)$G[x][y]=G[x][y−1]+φ(yx) ，同时对于一个 $x$x ,有 $y\le \lfloor \frac{m}{x}\rfloor$y≤⌊xm​⌋ ，因此也可以利用递推式在 $O\left(nlogn\right)$O(nlogn) 下预处理出。

令 $S\left[y\right]\left[z\right]\left[x\right]={\sum }_{x=1}^n{\sum }_{k\mid x}\frac{k}{\phi \left(k\right)}\mu \left(\frac{x}{k}\right){\sum }_{i=1}^y\phi \left(ix\right){\sum }_{j=1}^z\phi \left(jx\right)$S[y][z][x]=∑x=1n​∑k∣x​φ(k)k​μ(kx​)∑i=1y​φ(ix)∑j=1z​φ(jx)，
有递推式： $S\left[y\right]\left[z\right]\left[x\right]=S\left[y\right]\left[z\right][x-1]+F\left[x\right]\ast G\left[x\right]\left[y\right]\ast G\left[x\right]\left[z\right]$S[y][z][x]=S[y][z][x−1]+F[x]∗G[x][y]∗G[x][z]；
这个有三维，如果直接算的话，时间上肯定会爆炸，而且空间上也不能实现。
根据数论分块的理论，对 $x$x 进行分块讨论，当 $\lfloor \frac{n}{x}\rfloor =\lfloor \frac{m}{x}\rfloor$⌊xn​⌋=⌊xm​⌋ 时，对应 $x$x 的区间为 $[l,r]$[l,r] ，那么该段区间上的答案为 $S\left[n/l\right]\left[m/l\right]\left[r\right]-S\left[n/l\right]\left[m/l\right][l-1]$S[n/l][m/l][r]−S[n/l][m/l][l−1]。但是无法预处理出全部的 $S$S，我们只能在 $\lfloor \frac{n}{l}\rfloor$⌊ln​⌋ 比较小，即 $x$x 比较大的时候利用预处理的结果。当 $x$x 比较小的时候，可以利用递推式直接计算。但是大和小之间的界限是什么？这时，我们可以人为对 $y$y 和 $z$z 设置范围。当 $0\le y,z\le maxn$0≤y,z≤maxn 时，用分块；否则，用递推暴力。
预处理的那部分的时间复杂度小于 $O(n\ast max{n}^2)$O(n∗maxn2)
这样，总的时间复杂度为： $O(nlogn+n\ast max{n}^2+T(\sqrt{n}+n/maxn\left)\right)$O(nlogn+n∗maxn2+T(n ​+n/maxn))，实际上要更小。

代码实现：由于 $G$G 和 $S$S 都比较大，且每一维的长度都不相等，所以用 $vector$vector会比较省空间。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=1e5+5;
const int maxn=31;
vector<int>prime;
int mu[N],phi[N];
ll inv[N],F[N];
vector<ll>G[N],S[maxn][maxn];
bool vis[N];
void read(int &x)
{
    x=0;
    int f=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    x*=f;
}
void init()
{
    mu[1]=1;
    phi[1]=1;
    inv[1]=1;
    for(int i=2;i<=N-5;i++)//预处理欧拉函数和莫比乌斯函数
    {
        if(!vis[i])
        {
            prime.push_back(i);
            mu[i]=-1;
            phi[i]=i-1;
        }
        for(int j=0;j<prime.size()&&i*prime[j]<=N-5;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
            {
                mu[i*prime[j]]=-mu[i];
                phi[i*prime[j]]=phi[i]*phi[prime[j]];
            }
        }
    }
    for(int i=2;i<=N-5;i++)//递推逆元
        inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=N-5;i++)//预处理函数:F(x)
        for(int j=1;j*i<=N-5;j++)
            F[i*j]=(F[i*j]+1LL*mu[j]*i%mod*inv[phi[i]]%mod)%mod;
    for(int i=1;i<=N-5;i++)//预处理函数G[x][y]
    {
        G[i].push_back(0);//G[i][0]=0;
        for(int j=1;j<=(N-5)/i;j++)
            G[i].push_back(G[i][j-1]+1LL*phi[i*j]%mod);//G[i][j]=G[i][j-1]+phi[i*j];
    }
    for(int j=1;j<maxn;j++)
    {
        for(int k=1;k<maxn;k++)
        {
            S[j][k].push_back(0);
            for(int i=1;i<=(N-5)/max(j,k);i++)//除最大
                S[j][k].push_back((S[j][k][i-1]+F[i]*G[i][j]%mod*G[i][k]%mod)%mod);
        }
    }
}
ll solve(int n,int m)
{
    ll ans=0;
    if(n>m)
        swap(n,m);
    for(int i=1;i<=m/(maxn-1);i++)//用m除以界限
        ans=(ans+F[i]*G[i][n/i]%mod*G[i][m/i]%mod)%mod;
    for(int l=m/(maxn-1)+1,r=0;l<=n;l=r+1)
    {
        r=min(n,min(n/(n/l),m/(m/l)));
        ans=(ans+(S[n/l][m/l][r]-S[n/l][m/l][l-1]+mod)%mod)%mod;
    }
    return ans;
}
int main()
{
    int t,n,m;
    init();
    read(t);//cout<<"t= "<<t<<endl;
    while(t--)
    {
        read(n);
        read(m);
        printf("%lld\n",solve(n,m));
    }
    return 0;
}

参考博客1
参考博客2