APIO20 Device

문제

oj.uz/problem/view/APIO19_strange_device

문제 보기 - 이상한 기계 (APIO19_strange_device) :: oj.uz

parameter t에 대해, 순서쌍 (x, y)는 다음과 같이 정의된다. 

$x=(t+[\frac{t}{B}]) mod A$
$y=t mod B$

이 때, t의 disjoint한 구간 n개가 주어지고, 모든 구간의 합집합의 t에 대해, 서로 다른 (x, y)의 개수를 세야 한다.

 

$A, B<=10^18$

$L_i, R_i<=10^18$

$N<=10^6$

 

풀이

x, y에 대한 두 식이 모두 B에 대해 주기적으로 반복된다는 관찰로부터 시작한다.

Observation 1 : t에 대한 (x, y)의 반복 주기는 lcm(A, B+1)이다.

y는 단순히 B에 의해 반복됨으로, 주기는 $kB$꼴이다. 또한, B개의 원소가 지났을 때, x의 값은 $t$에 의해 B가 증가하고, $[\frac{t}{B}]$에 의해 1만큼 증가하여, 전체적으로 B+1만큼 증가한다. 이 증가 과정이 $k$회 반복된 후에는 A의 배수가 되어야 하기 때문에, 결국 B+1과 A의 최소공배수만이 주기가 될 수 있다.

 

따라서, 전체 주어진 구간들을 반복 주기 lcm(A, B+1)로 나눈 나머지에 대해 정리하고, 이의 합집합의 길이를 구하면 된다.

 

구간의 끝을 넘어가 돌아오는 경우와, 오버플로우가 발생하는 경우를 주의하자.

 

시간 복잡도 : $O(NlogN)$

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int N;
ll A, B, L;
pll P[MAXN+10];

map<ll, ll> M;

void addrange(ll l, ll r)
{
	M[l]++;
	M[r+1]--;
}

int main()
{
	scanf("%d%lld%lld", &N, &A, &B);
	for(int i=1; i<=N; i++) scanf("%lld%lld", &P[i].first, &P[i].second);

	L=__gcd(A, B+1);

	if(A/L>=(ll)1e18/B) L=1e18;
	else L=A/L*B;

	for(int i=1; i<=N; i++)
	{
		ll l=P[i].first, r=P[i].second;
		if(r-l+1>=L) return !printf("%lld\n", L);
		if(l%L<=r%L) addrange(l%L, r%L);
		else
		{
			addrange(l%L, L-1);
			addrange(0, r%L);
		}
	}

	M[L];
	ll t=0, ans=0;
	for(auto it=M.begin(); it!=M.end(); it++)
	{
		if(it->first==L) break;
		t+=it->second;
		if(t) ans+=next(it)->first-it->first;
	}
	printf("%lld\n", ans);
}