自动搬运

查看原文

来自洛谷，原作者为

	sgl654321 风起雨停，天又放晴

搬运于2025-08-24 22:44:43，当前版本为作者最后更新于2023-10-10 19:06:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

已经说的很清楚了。

解题思路

首先，如果 $\gcd(a_x,a_{x+1},\cdots,a_y)=z$，那么有 $\forall i\in[x,y],z|a_i$。我们可以据此把一个 $a_i$ 能整除的 $z_1,z_2\cdots$ 都标记出来，然后就有 $\text{lcm}(z_1,z_2,\cdots)|a_i$。

但是单单满足这个还不够，这只能保证 $z$ 是他们的公因数，不是最大公因数。

我们考虑贪心。显然，$\gcd(x,y)\le \gcd(k_1x,k_2y)$。 其中 $k_1,k_2$ 为正整数。考虑令所有的 $a_i=\text{lcm}(z_1,z_2,\cdots)$。如果此时的序列 $\{a\}$ 仍然不满足条件，那么如果 $a_i=k\text{lcm}(z_1,z_2,\cdots)$，那肯定就更不行了。

因此构造方案就是对于任意 $a_i$，把它能整除的 $z$ 都找出来，然后 $a_i$ 等于它们的最小公倍数。

接下来讲如何判断方案是否合法，即判断 impossible 的情况。由于 $\gcd$ 是有结合律的，我们可以考虑使用 ST 表来维护。具体的，设 $st_{i,j}$ 表示 $\text{lcm}(a_i,a_{i+1},\cdots a_{i+2^j-1})$。然后就可以用 $O(1)$ 的时间复杂度求出一个子串的 $\gcd$ 了。

参考代码

#include<bits/stdc++.h>
#define maxn 150010
using namespace std;
typedef long long ll;
struct node{
	ll x,y,z;
}ask[maxn];
ll n,a[maxn],m,x,y,z,f[maxn][20],b[maxn][20];
ll c[maxn],st[maxn][20],save,lo[maxn],num;
ll gcd(ll x,ll y){
	if(x==0)return y;
	return gcd(y%x,x);
}
ll lcm(ll x,ll y){
	return x/gcd(x,y)*y;
}
bool flag;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)c[i]=1;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		ask[i]=node{x,y,z};
		f[x][z]++;f[y+1][z]--;
	}
	for(int i=1;i<=16;i++)
		for(int j=1;j<=n;j++)
			b[j][i]=b[j-1][i]+f[j][i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=16;j++)
			if(b[i][j]>0)
				c[i]=lcm(c[i],j);
	for(int i=1;i<=n;i++)st[i][0]=c[i];
	for(int i=2;i<=n;i++)lo[i]=lo[i/2]+1; 
	for(int j=1;j<=19;j++)
		for(int i=1;i<=n;i++)
			if(i+(1<<j)-1<=n)
				st[i][j]=gcd(st[i][j-1],st[i+(1<<j-1)][j-1]);
	flag=1;
	for(int i=1;i<=m;i++){
		x=ask[i].x;y=ask[i].y;z=ask[i].z;
		save=lo[y-x+1];
		num=gcd(st[x][save],st[y-(1<<save)+1][save]);
	//	cout<<num<<endl;
		if(num!=z)flag=0;
	}
	if(!flag)cout<<"Impossible"<<endl;
	else{
		for(int i=1;i<=n;i++)	
			cout<<c[i]<<" ";
		cout<<endl;
	}
	return 0;
}