自动搬运

查看原文

来自洛谷，原作者为

	Link_Cut_qwq :)

搬运于2025-08-24 22:36:27，当前版本为作者最后更新于2022-02-15 00:26:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

传送门

在开始前我们先思考一个简化版：

$n$ 等于 $1$ 怎么办？

我们将 $a_1$ 拆成 $\gcd(a_1,m)\times x$，然后一次操作就相当于将 $a_1$ 变成 $\gcd(a_1,m)\times (x+1)$。

但是 $x$ 会就这样一直加下去吗？显然不是的。当 $\gcd(\frac{m}{\gcd(a_1,m)},x)>1$ 时，$\gcd(a_1,m)$ 会乘 $y$，$x$ 会除以 $y$。

但是上述操作只会进行大约 $\log m$ 次。因为 $\gcd(a_1,m)<=m$，所以不可能做超过 $\log m$ 次乘法。

因此我们可以尝试求出每次操作相比上一次 $x$ 加了多少，就能求出最终变换次数。

怎么求呢？

我们先求出所有当前 $\frac{m}{\gcd(a_1,m)}$ 的质因子的倍数中 $≥x$ 且值最小的数，这就是我们下一次操作时 $x$ 的值。然后更新 $\gcd(a_1,m)$ 和 $x$ 到下一次操作后的值。

就这样做大约 $\log m$ 次，直到 $\gcd(a_1,m)=m$ 就可以求出答案。

然后扩展到原题。

首先需要知道 $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$。

对于 $a_i$，我们发现前面的 $\gcd(a_1,a2,...,a_{i-1})$ 只有大约 $\log m$ 种可能。

为什么？

先证明每次从前面过来的 $\gcd$ 都是上一次的倍数。

我们考虑递推证明。

假设 $\gcd(m,a_1,a2,...,a_{i-1})$ 满足上述情况。若 $a_i$ 不变则很简单。现在有 $x$ 的影响。但是 $x$ 的质因子只要被乘进 $\gcd$ 里面就不会再出来了。所以 $\gcd(m,a_1,a2,...,a_i)$ 满足上述情况。

同时 $\gcd(m)$ 满足上述情况，顺着推下去即可。证毕。

然后很简单的结论：每次 $\gcd$ 改变都会乘一个数。最多乘 $\log m$ 次，所以只会有 $\log m$ 种可能。

于是对于前面过来的每个 $\gcd$，我们都按照 $n=1$ 操作一遍，只不过多了个变换次数上限。然后就可以求出每个位置的 $a_i$ 需要变换几次才能符合要求。取 $\max$ 即可。

因为分解质因数是 $O(\sqrt{m})$ 的，所以作者先分解然后直接用质因数做。复杂度多了一个 $\log$。

复杂度 $O(\sqrt{m}+n\log^2m)$

其实复杂度是不到的。因为里面大多数的数都没有 $\log m$ 个质因数。

代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define N 100010
using namespace std;

ull n,m,a[N],f[2][65][65],t[2][65],cnt[2],c[2][65],ans;

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%llu",&a[i]);
	ull x=2;
	while(m>1)
	{
		if(m%x==0) 
			m/=x,f[0][1][++c[0][1]]=x,x=1;
		x++;if(x*x>m) break;
	}
	if(m!=1) f[0][1][++c[0][1]]=m;
	t[0][2]=8e18;cnt[0]=1;
	ull now,cur;bool u;
	for(int i=1;i<=n;i++)
	{
		u^=1;cur=a[i];cnt[u]=0;now=0;
		memset(f[u],0,sizeof(f[u]));
		memset(c[u],0,sizeof(c[u]));
		for(int j=1;j<=cnt[u^1];j++)
		{
			cur+=(t[u^1][j]-now);now=t[u^1][j];
			ull p=t[u^1][j+1],w[60];int c1,nd;
			while(true)
			{
				c1=1;nd=0;
				for(int k=1;k<=c[u^1][j];k++)
					if(f[u^1][j][k]!=f[u][cnt[u]][c1])
						w[++nd]=f[u^1][j][k];
					else c1++;
				ull mi=8e18,q=-1;
				for(int k=1;k<=nd;k++)
					if(((cur-1)/w[k]+1)*w[k]-cur<=p-now)
						if(((cur-1)/w[k]+1)*w[k]-cur<mi)
							mi=((cur-1)/w[k]+1)*w[k]-cur,q=w[k];
				if(q==-1) break;
				now+=((cur-1)/q+1)*q-cur;cur=(cur-1)/q+1;
				cnt[u]++;
				for(int k=1;k<=c[u][cnt[u]-1];k++)
					f[u][cnt[u]][k]=f[u][cnt[u]-1][k];
				c[u][cnt[u]]=c[u][cnt[u]-1];
				f[u][cnt[u]][++c[u][cnt[u]]]=q;
				int s=c[u][cnt[u]];
				while(s>1&&f[u][cnt[u]][s]<f[u][cnt[u]][s-1])
					swap(f[u][cnt[u]][s],f[u][cnt[u]][s-1]),s--;
				t[u][cnt[u]]=now;
			}
		}
		ans=max(ans,now);t[u][cnt[u]+1]=8e18;
	}
	cout<<ans<<endl;
	return 0;
}