自动搬运

查看原文

来自洛谷，原作者为

	whiteqwq 寻找着梦与现实的交点 在哪呢 在哪呢

搬运于2025-08-24 22:31:11，当前版本为作者最后更新于2021-05-11 23:15:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P7575 「PMOI-3」公约数解题报告：

更好的阅读体验

题意

给定$n,m$以及一个长度为$n-1$的序列$x$（保证$x_i$互不相同），求：

$$\sum_{i_1=1}^m\sum_{i_2=1}^m\cdots\sum_{i_n=1}^m[\gcd(i_1,i_2)=x_1][\gcd(i_2,i_3)=x_2]\cdots[\gcd(i_{n-1},i_n)=x_{n-1}] $$

分析

好久没有反演了，反演一波。

这个式子看上去要硬上莫反，但由于$x_i$互不相同，因此不好直接反演。

考虑dp，设$f_{i,j}$表示考虑前$i$个数，且第$i$个数强制设为$j$的方案数，那么最后的答案为$\sum_{i=1}^m f_{n,i}$，且很容易列出转移方程：

$$f_{i,j}=\sum_{k=1}^m[\gcd(j,k)=x_i]f_{i-1,k}$$

这个式子可以上莫反了，化一化就可以得到：

$$f_{i,j\times x_i}=\sum_{k=1}^{\lfloor\frac{m}{x_i}\rfloor}f_{i-1,k\times x_i}\sum_{r\mid\gcd(j,k)}\mu(r)=\sum_{r\mid j}\mu(r)\sum_{k=1}^{\lfloor\frac{m}{x_i\times r}\rfloor}f_{i-1,k\times x_i\times r} $$

设$g_{i,j}=\sum_{k=1}^{\lfloor\frac{m}{j}\rfloor}f_{i,k\times j}$，那么上式可化简：

$$f_{i,j\times x_i}=\sum_{r\mid j}\mu(r)\times g_{i-1,x_i\times r} $$

式子仍然棘手，再次设$f'_{i,j}=f_{i,j\times x_i},g'_{i,j}=g_{i,j\times x_i}$，那么会有两个式子成立（分别从上面定义式与原式的化简式得来）：

$$g'_{i,j}=\sum_{j\mid k}^{\lfloor\frac{m}{x_i}\rfloor}f'_{k}\\f'_{i,j}=\sum_{r\mid j}\mu(r)\times g'_{i-1,r} $$

设$h_{i,j}=\mu(j)\times g_{i,j}$，那么我们惊奇地发现$g'$是$f'$的狄利克雷后缀和，$f'$是$h$的狄利克雷前缀和。

我们知道最开始的$f_1$，可以直接推出$f'_1$，然后可以通过狄利克雷后缀和推出$g'_1$，然后用$h$的定义推出$h_1$，再次用狄利克雷前缀和推出$f'$，然后推出$f_2$……

分析一下时间复杂度，由于狄利克雷前/后缀和的复杂度是$O(n\log \log n)$的，而我们进行狄利克雷前/后缀和的总数组大小为$\sum_{i=1}^n \frac{m}{x_i}\leqslant \sum_{i=1}^m\frac{m}{i}=m\ln m$（由于$x_i$互不相同），所以复杂度应该为$O(m\log m\log \log m)$。（$n$与$m$同阶）

代码

代码具体内容不需要定义这么多数组，两个就够用了。

目前最优解，欢迎吊打。

#include<stdio.h>
const int maxn=1000005,mod=998244353;
int n,m,cnt,ans;
int p[maxn],c[maxn],miu[maxn],x[maxn],f[maxn],g[maxn];
inline int add(int x,int y){
	return x+y>=mod? x+y-mod:x+y;
}
void sieve(int n){
	c[1]=miu[1]=1;
	for(int i=2;i<=n;i++){
		if(c[i]==0)
			p[++cnt]=i,miu[i]=mod-1;
		for(int j=1;j<=cnt;j++){
			if(i*p[j]>n)
				break;
			c[i*p[j]]=1;
			if(i%p[j]==0){
				miu[i*p[j]]=0;
				break;
			}
			miu[i*p[j]]=miu[i]==0? 0:(mod-miu[i]);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m),sieve(m);
	x[0]=1;
	for(int i=1;i<n;i++)
		scanf("%d",&x[i]);
	for(int i=1;i<=m;i++)
		f[i]=1;
	for(int i=1;i<n;i++){
		for(int j=1;j*x[i]<=m;j++)
			g[j]=f[j*x[i]];
		for(int j=1;j*x[i-1]<=m;j++)
			f[j*x[i-1]]=0;
		for(int j=1;j<=cnt&&p[j]<=m/x[i];j++)
			for(int k=(m/x[i])/p[j];k>=1;k--)
				g[k]=add(g[k],g[k*p[j]]);
		for(int j=1;j*x[i]<=m;j++)
			g[j]=1ll*miu[j]*g[j]%mod;
		for(int j=1;j<=cnt&&p[j]<=m/x[i];j++)
			for(int k=1;k*p[j]<=m/x[i];k++)
				g[k*p[j]]=add(g[k*p[j]],g[k]);
		for(int j=1;j*x[i]<=m;j++)
			f[j*x[i]]=g[j];
	}
	for(int i=1;i<=m;i++)
		ans=add(ans,f[i]);
	printf("%d\n",ans);
	return 0;
}