백준 26132번: Fair Division

https://www.acmicpc.net/problem/26132

26132번: Fair Division

---

비록 해당 대회에서 제일 약한 급의 문제이긴 하지만 ICPC World Finals 2021 문제입니다! 풀이는 약간의 수학 지식으로 진행됩니다.

---

우선 문제에서 주어진 순서대로 첫 round를 진행시켜 봅니다.

 

제일 먼저 캡틴이 $fm$만큼을 받아갑니다.

 

그리고, 2번째 선원이 $m$에서 $fm$을 제외한 부분에서 $f$를 곱한만큼, 즉 $f(1-f)m$을 가져갑니다.

 

3번째 선원의 경우 $f \left \{ m - fm - f \left (1-f \right ) m \right \} = f(1-f)^{2}m$을 가져가게 됩니다.

 

즉 첫 라운드에서 $k$번째 선원은 $fm(1-f)^{k-1}$ 만큼을 가져갑니다.

---

임의로 라운드 개념을 버린채 captain을 $1$, $n+1$, $\cdots$ 번째 선원이라고 가정한다면, 캡틴이 받은 loots의 총량은 다음과 같습니다.

$$ \sum \textrm{Captain} = \sum_{i=0}^{\infty} fm(1-f)^{in}$$

고등학교 수학에서 나오는 무한등비급수의 합을 사용하면 다음을 얻습니다.

$$ \sum \textrm{Captain} = \frac{fm}{1- (1-f)^{n}}$$

 

같은 방법으로 $k^{th}$ 선원은 다음 만큼을 얻게 됩니다.

$$ \sum \textrm{k-th pirate} = \frac{fm(1-f)^{k-1}}{1- (1-f)^{n}} = (1-f)^{k-1} \sum \textrm{Captain}$$

---

여기서 제가 $f=\frac{q}{p}$로 놓고 풀어버려서, 블로그에는 문제의 의도를 따른 채 $f=\frac{p}{q}$로 놓고 설명을 올리지만 코드는 다릅니다!

 

서로소 $p,q$에 대해 $f=\frac{p}{q}$로 놓게 되면, $1 \leq k \leq n$에 대해 위 k-th pirate 값이 모두 정수여야 하므로, $q^{n-1} | \sum \textrm{Captain}$ 입니다.

 

한편 $f=\frac{p}{q}$이므로

$$ \sum \textrm{Captain} = \frac{ q^{n-1}pm }{ q^{n} - (q-p)^{n} } $$

이에 따라

$$ \frac{ pm }{ q^{n} - (q-p)^{n} } \in \mathbb{Z} $$

입니다.

---

주어진 $n,m$에 대해 저 식을 만족하는 $q,p$쌍을 찾으면 끝납니다만, C/C++의 빈약한 자료형으로는 한계가 있습니다. 따라서 맘 편하게 Python3, PyPy3으로 내는 방법이 있고, magic number을 찾아 어떻게든 overflow 없이 푸는 방법이 있습니다.

 

저는 C/C++ 유저이므로, overflow 없는 최적의 $q,p$ 범위를 찾아보겠습니다.

 

우선 $n,m,p$를 고정했을 때 다음을 만족하는 $q$가 해당 $n,m,p$에 대해 상한입니다.

$$ pm = q^{n} - (q-p)^{n} $$

물론 이때 $q$는 $n,m,p$에 따라 급격히 변하지만, 저는 여기서 매우매우 rough하게 범위를 정했습니다.

$$ m = \frac{ q^{n} - (q-p)^{n} }{ p } \leq 10^{18} $$

위 식을 만족하는 $1 \leq p < q$가 하나라도 있는 $q$가 주어진 $n$에 대해 제가 탐색할 최대의 범위입니다. __int128로 전처리할때 $10^{36}$ 근방에서 overflow가 일어나니 조심해야 합니다.

---

한편, 혹시라도 $\frac{q^{n}-(q-p)^{n}}{p} \in \mathbb{Z}$ 가 항상 성립하는지를 궁금해할 수 있을 것 같습니다. 해당 식을 잘 인수분해하게 되면 분자의 인수 중 하나가 $p$이므로 다음을 얻습니다.

$$ \frac{q^{n}-(q-p)^{n}}{p} = q^{n-1} + q^{n-2}p + \cdots + qp^{n-2} + p^{n-1}$$

전처리를 하게 되면 대략 $n=6$일 때 $q \leq 4000$, $n=7$일 때 $q \leq 1000$에서 $q,p$쌍이 나타남을 알 수 있습니다.

 

의외로 아직 놓친 게 있는데, $n \leq 10^{6}$ 이라는 것입니다. 대략 $10^{6}$ 스케일까지 가면, $q=2$조차 overflow가 나서 $m$을 제대로 구할 수 없겠죠? 어느 시점부터 impossible한지도 생각해야 합니다.

 

rough하게 보면 $q=2$일 때조차 $m>10^{18}$인 $n$값을 찾는 것이고, 이는 쉽게 $n \geq 60$ 이라는 걸 알 수 있습니다.

---

ICPC가 공개한 Secret input data에 따르면, $n=6$일 때 $q \approx 4000$, 또는 $n = 59$ 등의 데이터가 여럿 있습니다. 이런 엣지 케이스 저격에 당하면 매우 귀찮기 때문에, precomputation을 그만큼 더 신경서야 하는 문제였습니다. 제 코드는 다음과 같습니다.

#include <stdio.h>

// I thought f = q/p ;)
int maxp[60] =
{
	0,0,0,0,0,0,
	4000,1000,400,200,100,90,
	50,50,50,50,50,50,
	46,37,31,26,23,20,
	17,15,14,12,11,10,
	10,9,8,8,7,7,
	6,6,6,5,5,5,
	5,4,2,2,2,2,
	2,2,2,2,2,2,
	2,2,2,2,2,2
};

__int128 power (__int128 x, int y);

int main(void) {
	
	int n;
	long long m;
	scanf("%d %lld", &n, &m);
	
	if (n >= 60) {
		printf("impossible");
		return 0;
	}
	
	int maxP = maxp[n];
	for (int P = 2; P <= maxP; P++) {
		for (int Q = 1; Q < P; Q++) {
			__int128 numerator = (__int128)Q * m;
			__int128 denominator = power(P,n) - power(P-Q,n);
			if (numerator % denominator == 0) {
				printf("%d %d", Q, P);
				return 0;
			}
		}
	}
	
	printf("impossible");
	return 0;
}

__int128 power (__int128 x, int y) {
	__int128 result = 1;
	while(y) {
		if (y & 1) {
			result = result * x;
		}
		x = x * x;
		y >>= 1;
	}
	return result;
}

(C11, 320ms, 1116KB, 제출번호 54599414)

---

시간복잡도가 $O \left ( \textrm{maxP} ^{2} \log n \right )$이기 때문에, 괜히 루프 안에서 분모 분자의 gcd를 체크하거나, 루프 범위를 늘려버리면 실행 시간이 급격히 늘어납니다.