专栏文章

题解：P13645 Totient with Divisors

FFeather_MoonDestr0yer
P13645题解参与者 25已保存评论 30

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
30 条
当前快照
1 份
快照标识符
@miofwrlg
此快照首次捕获于
2025/12/02 18:33
3 个月前
此快照最后确认于
2025/12/02 18:33
3 个月前
查看原文
题目传送门

题意

给你多组询问，求：
∑i=1n∑j=1mφ(i)φ(j)σ(ij)\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)\sigma(ij)
其中 1≤T,n,m≤1051\leq T,n,m\leq 10^5。

分析

不妨设 n≤mn \leq m。
首先我们肯定要把 σ(ij)\sigma(ij) 拆开。
然后这里有一个结论：
σ(ij)=∑x∣i∑y∣jiyx[gcd⁡(x,y)=1]\sigma(ij)=\sum_{x\mid i}\sum_{y\mid j}\dfrac{iy}{x}[\gcd(x,y)=1]
该结论的简要证明
感性证明
我们有:
σ(x)=∏i(1+pi+pi2+⋯+piai)\sigma(x)=\prod_{i}(1+p_i+p_i^2+\cdots+p_i^{a_i})
每个质因子可以独立处理。
xx 和 yy 本质上枚举了 ii 和 jj 的所有质因子组合。
gcd⁡(x,y)=1\gcd(x,y)=1 保证了每个质因子 xx 和 yy 中有一个指数为 00。
那么 iyx\dfrac{iy}{x} 就可以取到一个质因子在 ijij 中的所有指数。
理性证明
考虑每个质因子 pp 独立处理。
令 vp(n)v_p(n) 表示质因子 pp 整除 nn 的最高幂次。
由 x∣i,y∣jx\mid i,y\mid j 易得 0≤vp(x)≤vp(i),0≤vp(y)≤vp(j)0 \leq v_p(x) \leq v_p(i),0 \leq v_p(y) \leq v_p(j)。
由 gcd⁡(x,y)=1\gcd(x,y)=1，易得 min⁡(vp(x),vp(y))=vp(1)=0 \min(v_p(x),v_p(y))=v_p(1)=0。
  • 当 vp(x)=0v_p(x)=0 且 vp(y)≠0v_p(y) \neq 0 时，vp(iyx)=vp(i)+vp(y)v_p(\dfrac{iy}{x})=v_p(i)+v_p(y)，恰好取得 [vp(i)+1,vp(i)+vp(j)=vp(ij)][v_p(i)+1,v_p(i)+v_p(j)=v_p(ij)] 每个数各一次。
  • 当 vp(y)=0v_p(y)=0 时，vp(iyx)=vp(i)−vp(x)v_p(\dfrac{iy}{x})=v_p(i)-v_p(x)，恰好取得 [0,vp(i)][0,v_p(i)] 每个数各一次。
故 vp(iyx)v_p(\dfrac{iy}{x}) 不重不漏的取了 [0,vp(ij)][0,v_p(ij)] 每个数各一次。
而所有质因子的每种组合都会被取一遍，故结论成立。
最难点已过，恭喜你切掉一道黑题。
接下来就是我们喜闻乐见的推式子时间： ∑i=1n∑j=1mφ(i)φ(j)σ(ij)\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)\sigma(ij) 用上述结论把 σ(ij)\sigma(ij) 替掉，得： ∑i=1n∑j=1mφ(i)φ(j)∑x∣i∑y∣jiyx[gcd⁡(x,y)=1]\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)\sum_{x\mid i}\sum_{y\mid j}\dfrac{iy}{x}[\gcd(x,y)=1] 经典的拆 gcd⁡\gcd：
∑i=1n∑j=1mφ(i)φ(j)∑x∣i∑y∣jiyx∑d∣gcd⁡(x,y)μ(d)\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)\sum_{x\mid i}\sum_{y\mid j}\dfrac{iy}{x}\sum_{d\mid \gcd(x,y)}\mu(d)
交换求和顺序，把 dd 外提：
∑d=1nμ(d)(∑d∣xn∑x∣iniφ(i)x)(∑d∣ymy∑y∣jmφ(j))\sum_{d=1}^n \mu(d)(\sum_{d \mid x}^n\sum_{x\mid i}^n \dfrac{i\varphi(i)}{x})(\sum_{d\mid y}^m y\sum_{y \mid j}^m\varphi(j))
令 x=dX,i=xI,y=dY,j=yJx=dX,i=xI,y=dY,j=yJ：
∑d=1nμ(d)(∑X=1⌊n/d⌋∑I=1⌊n/dX⌋Iφ(dXI))(∑Y=1⌊m/d⌋dY∑J=1⌊m/dY⌋φ(dYJ))\sum_{d=1}^n \mu(d)(\sum_{X=1}^{\lfloor n/d \rfloor}\sum_{I=1}^{\lfloor n/dX \rfloor}I\varphi(dXI))(\sum_{Y=1}^{\lfloor m/d \rfloor} dY\sum_{J=1}^{\lfloor m/dY \rfloor}\varphi(dYJ))
把 dYdY 中的 dd 往外提，交换 J,YJ,Y 的求和顺序：
∑d=1ndμ(d)(∑X=1⌊n/d⌋∑I=1⌊n/dX⌋Iφ(dXI))(∑J=1⌊m/d⌋∑Y=1⌊m/dJ⌋Yφ(dJY))\sum_{d=1}^{n}d\mu(d)(\sum_{X=1}^{\lfloor n/d \rfloor}\sum_{I=1}^{\lfloor n/dX \rfloor}I\varphi(dXI))(\sum_{J=1}^{\lfloor m/d \rfloor}\sum_{Y=1}^{\lfloor m/dJ \rfloor}Y\varphi(dJY))
注意两个括号是相同的形式，我们令：
F(x,y)=∑i=1x∑j=1⌊x/i⌋jφ(ijy)F(x,y)=\sum_{i=1}^x\sum_{j=1}^{\lfloor x/i \rfloor}j\varphi(ijy)
令 T=ijT=ij：
F(x,y)=∑T=1xφ(Ty)∑j∣Tj=∑T=1xφ(Ty)σ(T)\begin{aligned} F(x,y)&=\sum_{T=1}^x\varphi(Ty)\sum_{j \mid T}j\\ &=\sum_{T=1}^x\varphi(Ty)\sigma(T)\\ \end{aligned}
注意到这东西可以递推：
F(x,y)=F(x−1,y)+φ(xy)σ(x)F(x,y)=F(x-1,y)+\varphi(xy)\sigma(x)
将其带入原式，得：
∑d=1ndμ(d)F(⌊nd⌋,d)F(⌊md⌋,d)\sum_{d=1}^nd\mu(d) F(\lfloor \dfrac{n}{d} \rfloor,d) F(\lfloor \dfrac{m}{d} \rfloor,d)
然后就可以用类似 P4240 的方法做了！具体的说：
然后你会发现这个时候 FF 里面是带 dd 的不能直接的数论分块。我们考虑平衡。
套路地，我们把整个式子换元换出来。我们令：
G(n,m,k)=∑d=1kdμ(d)F(⌊nd⌋,d)F(⌊md⌋,d)G(n,m,k)=\sum_{d=1}^kd\mu(d) F(\lfloor \dfrac{n}{d} \rfloor,d) F(\lfloor \dfrac{m}{d} \rfloor,d)
然后我们发现当 dd 很大的时候 ⌊nd⌋,⌊md⌋\lfloor \dfrac{n}{d} \rfloor,\lfloor \dfrac{m}{d} \rfloor 很小，这是不是意味着我们可以预处理一部分 GG？
首先我们可以用递推把所有的 FF 给预处理出来，时间复杂度是调和级数级别的即 O(nln⁡n)\mathcal{O}(n \ln n) 的。
设置一个阈值 SS，⌊nd⌋≤S\lfloor \dfrac{n}{d} \rfloor \leq S 的部分预处理。用人话说，我们要把 G(x,y,z)G(x,y,z) 中 x≤Sx \leq S 的所有 G(x,y,z)G(x,y,z) 的值预处理出来。
因为第三维是可以递推 O(1)\mathcal{O}(1) 求的，xx 有 SS 种取值，y×z≤my \times z \leq m，预处理的时间复杂度是 O(mS)\mathcal{O}(mS) 的。
接下来我们就可以数论分块了，如果预处理过了数论分块算复杂度是 O(Tn)\mathcal{O}(T \sqrt{n}) 的，没预处理过暴力算。因为我们已经把 ⌊nd⌋≤S\lfloor \dfrac{n}{d} \rfloor \leq S 的部分预处理了，所以剩下没预处理的一定满足 d≤⌊nS+1⌋d\le \lfloor\dfrac{n}{S+1}\rfloor，时间复杂度为 O(nTS)\mathcal{O}(\dfrac{nT}{S})。
总时间复杂度 O(nTS+Tn+mS+nln⁡n)\mathcal{O}(\dfrac{nT}{S}+T \sqrt{n}+mS+n \ln n)。反正 n,mn,m 同阶，SS 取 T\sqrt{T} 可以达到时间复杂度 O((n+m)T+Tn+nln⁡n)O((n+m)\sqrt{T}+T\sqrt{n}+n \ln n)。
代码
代码写的就是一坨大家不要拿我的代码做参考
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,L=405,TT=998244353;
int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
void write(int x){
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
int pri[N],top;
int flg[N];
int mu[N],phi[N];
long long d[N],sp[N];
void init(int n){
	mu[1]=1;phi[1]=1;d[1]=1;
	for(int i=2;i<=n;i++){
		if(!flg[i]){
			pri[++top]=i;
			phi[i]=i-1;
			mu[i]=-1;
			d[i]=i+1;
			sp[i]=i+1;
		}
		for(int j=1;j<=top;j++){
			int pri_j=pri[j];
			if(i*pri_j > n)break;
			flg[i*pri_j]=1;
			if(i%pri_j==0){
				sp[i*pri_j]=sp[i]*pri_j+1;
				d[i*pri_j]=d[i]/sp[i]*sp[i*pri_j];
				phi[i*pri_j]=phi[i]*pri_j;
				mu[i*pri_j]=0;
				break;
			}
			phi[pri_j*i]=phi[i]*phi[pri_j];
			d[pri_j*i]=d[pri_j]*d[i];
			mu[i*pri_j]=-mu[i];
			sp[i*pri_j]=1+pri_j;
		}
	}
	for(int i=1;i<=n;i++)d[i]=d[i]%TT;
}//筛 
int T,n,m;
int S;
int f[L][N];
int af[N][505];
void make_f(){
	for(int i=1;i<=S;i++){
		for(int j=1;i*j<=(N-5);j++){
			f[i][j]=((long long)f[i-1][j]+((long long)phi[i*j]*d[i]%TT))%TT;
		}
	}
	for(int j=1;j<=(N-5)/S;j++){//注意是 N/S 不是 S 
		for(int i=1;i*j<=(N-5);i++){
			af[i][j]=((long long)af[i-1][j]+((long long)phi[i*j]*d[i]%TT))%TT;
		}
	}
}//预处理 f，懒得用 vector 所以我用了静态数组 
vector<int> g[L][L];
int now;
void make_g(){
	for(int i=1;i<=S;i++){
		for(int j=1;j<=S;j++){
			g[i][j].push_back(0);
			for(int k=1;i*k<=(N-5) && j*k<=(N-5);k++){
				g[i][j].push_back(((long long)g[i][j][k-1]+(long long)k*(long long)mu[k]%TT*(long long)f[i][k]%TT*f[j][k]%TT+TT)%TT);
			}
		}
	}
}//预处理 g 
int calc(int n,int m){
	int ret=0,l=1,r=0;
	while(l<=n){
		r=min(n/(int)(n/l),m/(int)(m/l));
		if(r>n)r=n;
		if((n/l)<=S && (m/l)<=S){
			ret=((long long)ret+(long long)g[n/l][m/l][r]-g[n/l][m/l][l-1]+TT)%TT;
		}else{
			for(int k=l;k<=r;k++)ret=((long long)ret+(long long)k*(long long)mu[k]%TT*(long long)af[n/l][k]%TT*af[m/l][k]%TT+TT)%TT;
			//暴力计算 
		}
		l=r+1;
	}
	return ret;
}
signed main(){
	T=read();S=200;
	init(N-5);
	make_f();make_g();
	while(T--){
		n=read(),m=read();
		if(n>m)swap(n,m);
		write(calc(n,m));putchar('\n');
	}
	return 0;
}

后记

为出题喜欢用经典结论的出题人献上由衷的祝福。
我劝你们家里多备几个【数据删除】。

评论

共 30 条评论，欢迎与作者交流。

正在加载评论...