P4240 毒瘤之神的考验

放弃复建……

观前提醒

本文含有巨量 公式，请确保渲染完成以获得最优的阅读体验。

题目简介

题目名称：毒瘤之神的考验
题目来源：洛谷月赛
评测链接：https://www.luogu.com.cn/problem/P4240

形式化题意：求：

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(i\ast j)$$

对 取模。多测。

数据范围：

第一步，得把那个看起来非常恶心的式子给化开。

考虑 函数的定义式：

$$\varphi(n)=\sum_{i=2}^{n}[\gcd(i,n)=1]$$

与 互质的数的个数，但我们还有一个更有用的式子：

$$\varphi(n)=n\times\prod_{p\mid n}\frac{p-1}{p}$$

其中 为质数。

所以，可以得到：

$$\varphi(i\times j)=i\times j\times\prod_{p\mid (i\times j)}\frac{p-1}{p}$$

而

$$\varphi(i)\times\varphi(j)=i\times j\times\prod_{p\mid i}\frac{p-1}{p}\times\prod_{p\mid j}\frac{p-1}{p}$$

容易发现，对于 ，计算了 质因子分解的并集，而 和 的分开计算使得 的交集被重复计算了一次，所以我们需要除一遍 让两个式子达到平衡。

也就可以得到：

$$\frac{\varphi(i)\varphi(j)}{\varphi(\gcd(i,j))}=\frac{\varphi(i\times j)}{\gcd(i,j)}$$

从而化简出：

$$\varphi(i\times j)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}$$

至此，我们完成了本题的第一步。然后就是基本的反演推导（默认 ）：

$$\begin{align} \sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(ij)&=\nonumber \sum_{i=1}^{n}\sum_{j=1}^{m}\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi\big(\gcd(i,j)\big)} \\&=\nonumber \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d=1}^{n}\frac{\varphi(i)\varphi(j)d}{\varphi(d)}[\gcd(i,j)=d] \\&=\nonumber \sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(id)\varphi(jd)\frac{d}{\varphi(d)}[\gcd(i,j)=1] \\&=\nonumber \sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(id)\varphi(jd)\frac{d}{\varphi(d)}\sum_{k\mid\gcd(i,j)}\mu(k) \\&=\nonumber \sum_{d=1}^{n}\frac{d}{\varphi(d)} \sum_{k=1}^{\lfloor\frac{n}{k}\rfloor}\mu(k) \sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\varphi(idk) \sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}\varphi(jdk) \end{align}$$

我们设 ，换枚举 为枚举 ，此时 变成了 的因数：

$$\begin{align} \mathrm{result} &=\nonumber \sum_{T=1}^{n} \sum_{d\mid T}\mu(\frac{T}{d})\frac{d}{\varphi(d)} \sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT) \sum_{j=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(jT) \end{align}$$

需要 的时间枚举，后半段 可以通过 时间预处理， 部分可以数论分块 时间预处理。

所以我们的时间复杂度为 ，至此，可以通过第一个 。

---

我们设：

$$\begin{align} f(n)&=\nonumber\sum_{d\mid n}\mu(\frac{n}{d})\frac{d}{\varphi(d)} \\ g(T,n)&=\nonumber \sum_{i=1}^{n}\varphi(iT) \end{align}$$

化简原式：

$$\mathrm{result}= \sum_{T=1}^{n}f(T)\cdot g(T,\lfloor\frac{n}{T}\rfloor)\cdot g(T,\lfloor\frac{n}{T}\rfloor)$$

前文已知， 可以在 时间内预处理出来，而根据观察，发现 存在递推公式：

$$g(T,n)=g(T,n-1)+\varphi(Tn)$$

所以 的预处理时间也是 。

所以现在的时间复杂度优化关键就在于前面的枚举了。我们将整个式子用函数表示：

$$S(n,x,y)=\sum_{T=1}^{n}f(T)\cdot g(T,x)\cdot g(T,y)$$

可以发现一个递推式：

$$S(n,x,y)=S(n-1,x,y)+f(n)\cdot g(n,x)\cdot g(n,y)$$

而对于中间的一段来说， 是相等的，所以可以考虑数论分块，写成差分形式：

$$\sum_{\lfloor\frac{n}{l}\rfloor=\lfloor\frac{n}{r}\rfloor,\lfloor\frac{m}{l}\rfloor=\lfloor\frac{m}{r}\rfloor,i=l}^{r} S(i,\lfloor\frac{n}{i}\rfloor,\lfloor\frac{m}{i}\rfloor) = S(r,\lfloor\frac{n}{l}\rfloor,\lfloor\frac{n}{l}\rfloor)- S(l,\lfloor\frac{n}{l}\rfloor,\lfloor\frac{n}{l}\rfloor)$$

那么，我们可以在 的时间内解决这个问题，至此，我们啥也通过不了。

---

容易发现，如果我们对 的所有 进行预处理的话，可以做到 的查询，但是预处理时空复杂度会上升到 ，所以我们考虑平衡规划阈值 ，我们只处理到 ，对后面的我们进行数论分块暴力查。

所以时间复杂度可以做到：，当 的时候取得最优。

AC Code

// ----- Eternally question-----
// Problem: P4240 毒瘤之神的考验
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4240
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-06-30 08:39:28
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10,MAXB=50;
const int Mod=998244353;
const int Uni=30;
bool Vis[MAXN];
int Mu[MAXN],Phi[MAXN],pri[MAXN],Tot;
bool is[MAXN];
int *G[MAXN],*S[MAXB][MAXB],F[MAXN];
int N,M,Test,inv[MAXN];
inline void sieve(int n)
{
	Mu[1]=Phi[1]=inv[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!is[i]) pri[++Tot]=i,Mu[i]=-1,Phi[i]=i-1;
		for(int j=1;j<=Tot&&i*pri[j]<=n;++j)
		{
			is[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				Mu[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);
		}
	}
}
inline void init(int n)
{
	for(int i=2;i<=n;++i) inv[i]=Mod-(ll)Mod/i*inv[Mod%i]%Mod;
	for(int i=1;i<=n;++i) for(int j=1;i*j<=n;++j) F[i*j]=(F[i*j]+(ll)i*inv[Phi[i]]%Mod*Mu[j]%Mod+Mod)%Mod;
	for(int i=1;i<=n;++i)
	{
		G[i]=new int [n/i+1];
		G[i][0]=0;
		for(int j=1;j<=n/i;++j) G[i][j]=(G[i][j-1]+(ll)Phi[i*j])%Mod;
	}
	for(int j=1;j<=Uni;++j)
		for(int k=1;k<=Uni;++k)
		{
			int len=(n/std::max(j,k));
			S[j][k]=new int [len+1];
			S[j][k][0]=0;
			for(int i=1;i<=len;++i) S[j][k][i]=(S[j][k][i-1]+(ll)F[i]*G[i][j]%Mod*G[i][k]%Mod)%Mod;
		}
}
inline ll solve(int n,int m)
{
	if(n>m) std::swap(n,m);
	ll ans=0;
	for(int i=1;i<=m/Uni;++i) ans=(ans+(ll)F[i]*G[i][n/i]%Mod*G[i][m/i]%Mod)%Mod;
	for(int l=m/Uni+1,r;l<=n;l=r+1)
	{
		r=std::min(n/(n/l),m/(m/l));
		ans=(ans+(ll)(S[n/l][m/l][r]-S[n/l][m/l][l-1]+Mod)%Mod+Mod)%Mod;
	}
	return ans;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	sieve(MAXN-10),init(MAXN-10);
	while(Test--)
	{
		read(N,M);
		write(solve(N,M),'\n');
	}
	return 0;
}
/*

*/