2013 IMO Problem 1 / BOJ 15948 간단한 문제

2018 UCPC Problem K 와 2013 IMO Problem 1이 사실상 같은 문제다. 정확히는 UCPC 문제의 출처가 이 문제고, 저 UCPC 문제 포스팅을 하려다 보니 그냥 원본 문제도 같이 포스팅하려고 한다.

 

문제

임의의 자연수 $n$과 $k$에 대하여, 다음을 만족하는 $k$개의 자연수 $m_1, m_2, \dots m_k$ 가 있음을 보여라.

$$1 + \frac{2^k-1}{n} = (1 + \frac{1}{m_1})(1+\frac{1}{m_2}) \cdots (1+\frac{1}{m_k})$$

 

 

 

 

 

 

 

풀이 1 : 수학적 귀납법

$k$에 대한 수학적 귀납법을 써 보자. $k = 1$ 일 때, 좌변은 $1 + \frac{1}{n}$ 이고, $m_1 = n$ 이면 되므로 임의의 $n$에 대해서 잘 성립한다.

어떤 자연수 $u$에 대해 $k = u$ 일 때 임의의 $n$에 대하여, 위 조건을 만족하는 $m_1$부터 $m_u$ 까지가 있다고 가정하자. 이제 $k$ 를 하나 늘렸을 때,

 

만약 $n$이 짝수라면, 다음이 성립한다.

$$1 + \frac{2^{u+1}-1}{n} = \left(1 + \frac{2^u-1}{n/2}\right) \left(1 + \frac{1}{n + 2^{u+1}-2}\right) $$

 

만약 $n$이 홀수라면, 숫자만 약간 바꿔 주면 된다.

$$1 + \frac{2^{u+1}-1}{n} = \left(1 + \frac{2^u-1}{(n+1)/2}\right) \left(1 + \frac{1}{n}\right) $$

 

두 경우 모두, 지수를 하나 줄이면서 원래의 형태를 유지한다. 즉, $u$개에 대해 풀 수 있다면, 어떤 $n$을 주든 $u+1$개에 대해서도 풀 수 있음을 보였으므로 귀납법이 완성된다.

 

 

풀이 2 

UCPC 2018 팀연습을 돌 때 나랑 Diordhd가 생각했던 풀이는 위 귀납법과 약간 다르다. 우리가 그때 생각했던 내용과 거의 똑같은 풀이를 AoPS의 m.candales가 적어서, 기술에 약간 참고했다.

 

우리가 다음 문제를 풀고자 한다고 생각해 보자.

 

$$1 + \frac{2^k-1}{n} = (\frac{m_1}{n})(\frac{m_2}{m_1}) \cdots (\frac{m_k}{m_{k-1}})$$

 

일단 $m_k$ 를 $n+2^k-1$ 로 고정해 버리고 나면, 나머지는 대충 잘 집어 넣어줘도 상관이 없다. 그런데 문제는, 우리는 $\frac{x+1}{x}$ 형태의 수밖에 쓸 수가 없다. 즉, 어떻게 잘 점프를 뛰어서, 우리가 변형한 문제의 숫자들이 사실은 잘 약분이 되게 하여 모든 수가 $\frac{x+1}{x}$ 형태가 된다면 목표를 달성한 것이다. 이 과정에서, 우리는 숫자를 하나 추가할때마다 분모는 매번 $n$으로 고정한 채 분자를 늘리는 것처럼 생각할 수 있다. 즉, $(\frac{m_1}{n})(\frac{m_2}{m_1})$ 의 곱셈은 분자를 $m_1$에서 $m_2$로 점프한 것으로 간주하겠다는 의미이다. 이 관점에서 우리는 정확히 $2^k-1$ 만큼 분자를 늘려야 하며, 늘릴 수 있는 기회는 $k$번 있다.

 

예를 들어, $k = 6, n = 51$ 을 생각해 보자. 우리는 $n = 51$ 에서 시작해서, 정확히 $n' = 51 + 63 = 114$ 를 향해야 한다. 이때, 첫번째 수로 $\frac{52}{51}$ 을 쓸 수 있다. 즉 처음에 1만큼 점프할 수 있다.

 

이제, $\frac{53}{52}$ 로도 점프할 수 있지만, 사실 1만큼 점프는 아무때나 할 수 있다. 그리고 우리는 생각보다 멀리 가야 한다 ($k$보다 일반적으로 $2^k-1$은 훨씬 더 큰 수니까, 일단 최대한 멀리 뛰어가고 싶다.)

 

그러니 다음 수는 최대한 먼 점프인 $\frac{56}{52}$ 로 뛰자 (이는 14/13이니까 "뛸 수 있는 수" 이다)

 

같은 이유로 $\frac{64}{56}$ 까지 뛸 수 있다. 지금까지 3번 점프를 썼고, 아직 3번 더 남았다.

바로 $\frac{96}{64}$, $\frac{112}{96}$, $\frac{114}{112}$ 로 열심히 뛰어가면 114에 닿을 수 있다.

 

 

이제, 점프 간격을 잘 보면, 1, 4, 8, 32, 16, 2 로 뛰었음을 알 수 있고, 이는 사실 $2^t$ 형태를 $2^{k-1}$ 까지 썼음을 관찰할 수 있다. 

 

 

즉, 다음을 생각하자. 

 

$n$보다 크(거나 같으)면서 가장 작은 $2^{k-1}$ 의 배수를 잡자. 즉, $n = 2^{k-1}q-r$ 인 $0 \leq r \leq 2^{k-1}$ 을 찾자는 의미이다.

그리고, $r$의 binary expression을 생각해 보면, $r$은 많아야 $k$비트에 들어갈 것이다. 일단 앞에 Leading zero를 허용해서, $k$비트의 이진수로 나타내었다고 하자. 그리고 $r$의 이진수 표현에서 1인 인덱스를 낮은 것부터 $a_1, a_2, \dots a_l$ 이라고 하자. (즉, $r = 2^{a_1} + 2^{a_2} \dots 2^{a_l}$이다)

이 $l$은 많아야 $k-1$인데, $r$에 0인 비트가 있다면 $k$보다 작을 것이다. 모자란 자리를 채우기 위해, 이번에는 $r$의 이진수 표현에서 0인 인덱스를 높은 것부터 (큰 자리부터) $a_{l+1} \dots a_{k}$ 까지 채워넣자. 1인 자리와 0인 자리를 모두 세었으니 이 수열 $a$는 반드시 정확히 $k$개이다.

 

이제 $n$을 다음과 같이 뛰어가면 된다. $(n_1 = n)$

$$n_i = n + \sum_{j = 1}^{i-1} 2^{a_j}$$

이러면 $n_{k+1}$ 는 $2^{a_i}$ 를 모두 더한 셈이 되며, $a_i$ 는 0부터 $k-1$ 까지의 permutation이므로 $n_{k+1} = 2^k-1+n$ 이 성립한다. 따라서, 이 '점프' 가 반드시 항상 모든 위치에서 가능함을 보이자. 즉, $2^{a_i} | n_i$ 임을 보이면 된다.

 

$1 \leq i \leq l$, 즉 $r$에서 1의 인덱스 들에 대해서는, $n_i$ 는 $2^{k-1}q$에서 $2^{a_l}$, $2^{a_{l-1}}$ ... 들을 정확히 $2^{a_{i}}$ 까지 빼낸 값이다. 잘 보면, $2^{k-1}q$ 도 $2^{a_i}$의 배수이고, 거기서 뺀 모든 수들도 $2^{a_i}$의 배수이다. 따라서, 그 결과인 $n_i$ 도 $2^{a_i}$의 배수.

 

$l+1 \leq i \leq k$에서는, 더 자명한데, 일단 우리가 앞에서 $l$개를 점프해서 $2^{k-1}$ 의 배수를 만들었다는 사실에 주목하자. 이제 남은 인덱스들을 큰 것부터 더해나가므로, 우리가 이미 $2^{k-1}q$에 $2^{a_{l+t}}$ 까지를 더하더라도 결과가 $2^{a_{l+t+1}}$ 의 배수임이 변하지 않는다. 64에 16을 더해도 8이나 4의 배수임이 유지되는 것을 예로 들 수 있다.

 

따라서, 이렇게 점프를 뛰면 된다.

---

 

 

 

---

BOJ 15948, UCPC 2018 K

이 문제는 원래 문제보다 약간 꼬여 있다. 

주어진 $A_1, A_2 \dots A_k$ 에 대하여, 다음 조건을 만족하는 수열 $m_1$ 부터 $m_k$ 까지를 구하는 문제. 

$$1 + \frac{2^k-1}{n} = \left( \frac{A_1 + m_1}{m_1} \right) \left( \frac{A_2 + m_2}{m_2} \right) \cdots \left( \frac{A_k + m_k}{m_k}\right)$$

 

위 문제와 같은 형태로 풀기 위해, 문제에 추가적인 제약을 주자. $m_i$ 로 가능한 수를 $A_i$ 의 배수만 허용한다.

이제 그러면, $m_i = A_i x_i$ 로 쓸 때, 모든 $A_i$ 들이 약분되어 위 IMO 문제와 정확히 같아진다.  

 

$m$으로 가능한 수의 범위가 매우 크므로, 일단 $x_i$에 대해 위 IMO 문제를 그대로 코드로 옮긴 다음, 받아놓은 $A_i$ 를 곱해서 답하면 된다. 수학적 귀납법 풀이는 재귀함수로 작성하는 것이 매우 자연스러워지는데, 우리는 두번째 풀이를 잡았기 때문에 비트 인덱스를 잘 찾아서 돌리는 식으로 찾아야 했다. 그리고 위 과정에서 점프를 다 찾은 다음에는, 모든 분수를 적절히 약분도 해 줘야 한다.

 

#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int ll
#define MOD 1000000007
using namespace std;
typedef long long ll;

int n, m;
int twopow;
bool visit[55];
int a [55];
vector <int> ans;
int32_t main()
{
	usecppio
	cin >> n >> m;
	twopow = (1LL << m);
	for (int i = 0; i<m; i++)
		cin >> a[i];
	int target = ((n/twopow + 1) * twopow);
	int dist_left = target-n;
	ans.push_back(n);
	for (int i = 0; i<m; i++)
	{
		if (dist_left & (1LL<<i))
		{
			ans.push_back(ans.back()+(1LL << i));
			dist_left -= (1LL << i);
			visit[i] = true;
		}
	}
	for (int i = m-1; i>=0; i--)
		if (!visit[i])
			ans.push_back(ans.back() + (1LL << i));
	for (int i = 0; i<m; i++)
	{
		int g = __gcd(ans[i], ans[i+1]);
		printf("%lld ",(ans[i]/g) * a[i]);
	}
}