BOJ 21620 Math Homework

문제 링크입니다.

문제 요약

$M$개의 조건: 구간 $[x, y]$의 gcd가 $z$ 를 만족하고, 각 원소가 10억 이하인 길이 $N$의 수열 $A$를 하나 찾으세요.

필요한 만큼만

각 원소가 필요 이상으로 많은 약수를 가질 필요는 없습니다. 오히려 조건으로 걸리지 않은 약수를 갖게 된다면 다른 조건을 만족시키지 못할 수도 있습니다. 예를 들어, 두 조건 ([1, 1], 4)와 ([1, 2], 2)가 주어졌을 때 2번 원소가 꼭 필요한 약수인 2 외에 4를 약수로 갖게 된다면 두 번째 조건이 깨지게 됩니다.

이를 피하기 위해 각 원소마다 딱 조건으로 걸린 만큼만 약수를 넣어줄 겁니다. 이는 조건으로 걸린 GCD 값들의 최소공배수로 실현됩니다. 제한 조건에 의해 입력으로 들어올 수 있는 모든 GCD 값들의 LCM은 720720으로, 원소의 최대 크기인 10억을 넘지 않습니다.

각 조건을 구간 내의 각 원소에 LCM을 먹이는 업데이트이자, 구간 내의 원소들의 GCD를 요청하는 쿼리로 생각할 수 있습니다. 레이지 세그를 이용하면 업데이트와 쿼리를 모두 ${\cal O}(\lg N)$에 구할 수 있으니, 총 시간 복잡도 ${\cal O}(M \lg N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int tree[606060], lazy[606060];

void init(int now, int l, int r){
	tree[now] = lazy[now] = 1;
	if(l != r){
		init(now<<1, l, mid);
		init(now<<1|1, mid+1, r);
	}
}

void prop(int now, int l, int r){
	if(lazy[now] == 1) return;
	if(l != r){
		lazy[now<<1] = lcm(lazy[now], lazy[now<<1]);
		lazy[now<<1|1] = lcm(lazy[now], lazy[now<<1|1]);
	}
	tree[now] = lcm(tree[now], lazy[now]);
	lazy[now] = 1;
}

void upd(int now, int l, int r, int L, int R, int g){
	prop(now, l, r);
	if(L > r || l > R) return;
	if(L <= l && r <= R){
		lazy[now] = g; prop(now, l, r);
		return;
	}
	upd(now<<1, l, mid, L, R, g);
	upd(now<<1|1, mid+1, r, L, R, g);
	tree[now] = gcd(tree[now<<1], tree[now<<1|1]);
}

int qry(int now, int l, int r, int L, int R){
	prop(now, l, r);
	if(l > R || L > r) return 16*9*5*7*11*13;
	if(L <= l && r <= R) return tree[now];
	return gcd(qry(now<<1, l, mid, L, R), qry(now<<1|1, mid+1, r, L, R));
}

void print(int now, int l, int r){
	prop(now, l, r);
	if(l == r){
		cout << tree[now] << ' ';
		return;
	}
	print(now<<1, l, mid);
	print(now<<1|1, mid+1, r);
}

int L[151515], R[151515], G[151515];

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n, m; cin >> n >> m; init(1, 1, n);
	for(int i = 1; i <= m; i++){
		cin >> L[i] >> R[i] >> G[i];
		upd(1, 1, n, L[i], R[i], G[i]);
	}
	for(int i = 1; i <= m; i++) if(qry(1, 1, n, L[i], R[i]) != G[i]) return !(cout << "Impossible");
	print(1, 1, n);
}