P9027 题解

sgl654321 · 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;
}