2709번: 가장 작은 K
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 50)가 주어진다. 각 테스트 케이스는 정수 1개로 이루어져 있고, 이 수는 R(1 ≤ R ≤ 20)이다.
www.acmicpc.net
이 문제에서 $R\leq 19$인 경우까지는 단순하게 구할 수 있습니다.
$R=20$의 경우는 C에서는 스트링으로 처리해야하는데, 이 부분이 귀찮았던 저는 구글링으로 해결했습니다.(acmgnyr.org/year2008/h.out)
위 링크를 통해 물론 모든 $R$에 대한 정답을 알고 쉽게 정답 코드를 작성할 수도 있습니다.
또는 아래 설명할 원리를 통해 미리 각 $R$ 값에 대한 정답을 구한 뒤, 이를 배열에 집어넣는 방식으로 구현해도 됩니다.
우선 아주 작은 $x$에 대해 $2^{x}$ 의 값을 구해봅시다.
| $x$의 값 | $2^{x}$ 의 값 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
| 6 | 64 |
| 7 | 128 |
| 8 | 256 |
| 9 | 512 |
| 10 | 1024 |
우리가 알고 있듯이, $2^{x}\;\; mod\; 10$ 의 값은 $2,\;4,\;8,\;6$ 이 반복되어 나오며 주기가 4입니다.
따라서 $R=1$ 일 때 조건을 만족하는 $k=1,\;5,\;9,\;13,\cdots$ 입니다.
이제 이런 $k$에 대해 다시 표를 그려보겠습니다.
| $x$의 값 | $2^{x}$의 값 |
| 1 | 2 |
| 5 | 32 |
| 9 | 512 |
| 13 | 8192 |
| 17 | 131072 |
| 21 | 2097152 |
| 28 | 33554432 |
| 29 | 536870912 |
| 33 | 8589934592 |
이쯤에서 맨 끝 2자리만 보도록 합시다.
$R=2$ 일 때 조건을 만족하는 $k$의 값 $k=9,29$ 를 확인할 수 있습니다.
그러면 $2^{x}\;\;mod\;100$ 의 값의 주기가 20일까요?
일단 표에서 ($x=1$을 제외하고) $mod\;100$을 취했을 때 반복되는 값은 $32,12,92,72,52$입니다.
이 값에 각각 $2^{20}=1048576$ 을 곱하고 $mod\;100$ 을 취하여 값을 관찰해봅시다.
$32\times 1048576=32\;\;mod\;100$
$12\times 1048576=12\;\;mod\;100$
$92\times 1048576=92\;\;mod\;100$
$72\times 1048576=72\;\;mod\;100$
$52\times 1048576=52\;\;mod\;100$
그런데 20이 주기인지, 혹시 더 작은 값이 주기일 수는 없는지 의문을 가질 수도 있습니다.
반복되는 값 ($32,\;12,\;92,\;72,\;52$) 의 특징 상, 주기가 $l$ 일 때 $2^{l}=6\;\;mod\;10$ 이어야 합니다.
따라서 $l$이 될 수 있는 값은 $4,8,12,16$ 이 존재합니다.
그런데 $16\left ( =2^{4} \right ),\;256\left ( =2^{8} \right ),4096\left ( =2^{12} \right ),65536\left ( =2^{16} \right )$ 을 위에 곱해보면, 반복이 되지 않습니다.
그러므로 주기가 20인 것은 틀림 없습니다. ( $R=2$ 일 때 )
따라서 $R=2$ 일 때 조건을 만족하는 $k=9,29,49,69,\cdots$ 입니다.
이런 방법을 통해 $R=3$ 까지는 직접 구하는게 가능할 지도 모르겠습니다.
실제로 구해보면, $2^{89}=112\;\;mod\;1000$ 이고, 주기는 100입니다.
또, $R=4$에 대해 연구를 계속해보면,
$2^{89}=2112\;\;mod\;10^{4}$ 이고,
$2^{100},\;\;2^{200},\;\;2^{300},\;\;2^{400},\;\;2^{500}$ 을 직접 곱해보며 주기가 500임을 알 수 있습니다.
그러므로 다음과 같은 추측을 할 수 있습니다.
$R$ 의 값이 하나 늘어날 때마다 주기는 5배가 된다.
이제 이 추측만 가지고도 나머지 정답들을 차례대로 구할 수 있습니다.
증명을 하지 않더라도 문제를 푸는데 큰 지장은 없습니다. 일단 맞는 추측이니까요.
간단하게 $R$ 의 값과 그에 대응하는 최소의 $k$ 의 값, 그리고 그 때의 주기($\Delta$) 를 표로 써보겠습니다.
| $R$ 의 값 | 최소의 $k$ 의 값 | $\Delta$ |
| 1 | 1 | 4 |
| 2 | 9 | 20 |
| 3 | 89 | 100 |
| 4 | 89 | 500 |
| 5 | 589 | 2500 |
| 6 | 3089 | 12500 |
| 7 | 3089 | 62500 |
| 8 | 3089 | 312500 |
| 9 | 315589 | 1562500 |
| 10 | 315589 | 7812500 |
| 11 | 8128089 | 39062500 |
| 12 | 164378089 | 195312500 |
| 13 | 945628089 | 976562500 |
| 14 | 1922190589 | 4882812500 |
| 15 | 11687815589 | 24414062500 |
| 16 | 109344065589 | 122070312500 |
| 17 | 231414378089 | 610351562500 |
| 18 | 1452117503089 | 3051757812500 |
| 19 | 4503875315589 | 15258789062500 |
이 아래는 몇 가지 증명과 문제에 대해 조사하면서 알게된 사실을 써보고자 합니다.
넘기셔도 상관없습니다.
이 문제에 대해 조사하던 중, 이 문제가 아주 오래된 문제라는 걸 알게 됐습니다.
그러므로 간략하게 이 문제의 역사(?)를 소개해보겠습니다.
가장 최근에 이 문제가 등장한 대회는 2008년 ICPC Greater New York Region으로, H번에 등장했습니다.
(이 글을 쓴 시점의 저는 그렇게 알고 있습니다.)
그런데 대회 공식 사이트(acmgnyr.org/year2008/problems.shtml)에서는 이 문제의 출처를
1963년에 F. J. Gruenberger 가 쓴 "What Should We Compute?" 라는 문서로 언급하고 있습니다.
(F. J. Gruenberger, "What Should We Compute?", RAND Corporation, September 1963)
그러나 Gruenberger는 이 문제의 수학적인 증명에 관심을 두지 않았습니다.
Gruenberger의 주장은 겨우 $R\leq 20$이라는 작은 범위에서도 저런 큰 결괏값을 내는 문제가 있으므로
효율적인 알고리즘을 써서 문제를 해결해내자는 것입니다.
확실히 수학적인 관찰이나 증명과는 거리가 멉니다.
그래도 Gruenberger은
저 문제와 관련해서 우리가 사용한 추측이 언제 어디서 증명되었는지 출처를 남겼습니다.
우선
"정수 $R$ 이 어떤 값이든지 $2^{k}\;\;mod\;\;10^{R}$ 의 값이 $1$ 또는 $2$ 로만 이루어진 $k$ 값이 존재할 것이다."
라는 추측은 문제를 푸는 우리 입장에서 전제로 깔고 갔을 것입니다.
원칙적으로는 증명이 필요하죠.
이 정리는 1950년에 저널 <The American Mathematical Monthly> 에 그 증명이 소개되었다고 합니다.
또한
"$R$ 의 값이 $1$씩 늘어날 수록 주기($\Delta$)가 5배씩 커진다"
라는 추측은 대충 들어맞았으니 맞는 것 같다며 넘겼지만 증명이 필요하죠.
이 정리 또한 같은 저널에서, 1951년에 증명이 되었다고 합니다.
Gruenberger은 수학적인 측면은 이 정도만 언급한 뒤 문제를 푸는 알고리즘을 자신의 저서에서 설명해줍니다.
또한 Gruenberger은 $1\leq R\leq 20$ 에 대하여 정답을 실어놨습니다.
$R=20$ 일 때의 정답이 궁금하신 분은,
울프람알파를 이용하여 직접 구해보거나
공식 사이트에서 제공하는 output파일을 열어보거나
Gruenberger의 문서를 읽어보면 되겠습니다.
이제 위 문제의 출처에 대해 조금 더 파고들 차례입니다.
저널 <The American Mathematical Monthly> 을 1950년 전후로 뒤져보면 찾을 수 있습니다.
우선, 첫 번째 추측과 관련한 문제가 처음 등장한 시기는 1949년입니다.
(R. J. Walker, The American Mathematical Monthly, Vol. 56, No. 1 (Jan, 1949), pp. 39-40.)
원문은 다음과 같습니다.
4326. Proposed by R. J. Walker, Cornell University
Prove or disprove: 128 is the only power of 2 of two or more digits each of
which is a power of 2.
4327. Proposed by R. J. Walker, Cornell University
In attempting to solve the preceding problem we tried to show that for some
positive integer r no power of 2 had its last r digits all powers of 2. Show that this
attempt had to fail; in particular, show that for each r there exist powers of
2 each of whose last r digits is either 1 or 2.
이중 4327번이 우리가 찾는 문제였음을 알 수 있습니다. (in particular 이후부터 읽어보면 감이 올 것입니다.)
이렇게 저널에 투고된 문제는 1년 뒤 해결됩니다.
(R. J. Walker and E. P. Starke, The American Mathematical Monthly, Vol. 57, No. 5 (May, 1950), p. 350.)
초등적 정수론에서 Euler's Theorem, primitive root, proof by induction을 활용하여 해결했습니다.
그런데 제가 정수론을 수강하진 않았어서, 솔직히 증명은 이해 못했습니다.
(애초에 존재성 증명이 중요한 문제는 아니므로...)
두 번째 추측은 같은 해인 1950년에, 같은 저널에 투고되었습니다.
(L. A. Ringenberg, The American Mathematical Monthly, Vol. 57, No. 10 (Oct, 1950), pp. 686-691.)
원문은 다음과 같습니다.
In the sequence of powers of 2: 2, 4, 8, 16, 32, · · · , the units digits form a
sequence of period four. What periodic properties do the other digits have?
이는 1년 뒤인 1951년에 해결되었습니다.
(Aaron Buchman, The American Mathematical Monthly, Vol. 58, No. 6 (Jun - Jul, 1951), pp. 418-419)
위 출처의 증명은 다음과 같습니다.
우선 $n$번째 자리 수의 주기가 $k$ 라는 것은 다음 합동식이 성립함을 의미합니다.
(단, $s$는 $2^{s}$의 값이 최소한 $n$번째 자리의 수를 가지는 수)
$2^{s+k}\equiv2^{s}\;\;\;mod\;10^{n}$
그런데 위 합동식과 다음 합동식은 동치입니다.
$2^{s+k-n}\equiv2^{s-n}\;\;\;mod\;5^{n}$
후자에서 전자를 유도하는 과정은 $2^{s+k-n}=A\times5^{n}+2^{s-n}$ 이라고 놓음으로써 해결됩니다.
양변에 $2^{n}$을 곱했을 때 전자가 유도됩니다.
전자에서 후자를 유도하는 과정은 $2^{s+k}=B\times10^{n}+2^{s}$ 일 때 양변을 $2^{n}$으로 나누면 됩니다.
결과적으로 다음 식이 유도됩니다.
$2^{k}\equiv 1\;\;\;mod\;5^{n}$
그런데 Euler's Theorem을 생각하면 이제 $k=\phi\left ( 5^{n} \right )$ 임을 알 수 있습니다.
Euler's Totient Function의 성질에 따라 $k=4\times 5^{n-1}$ 이므로, $n$ 이 커짐에 따라 주기 $k$ 도 5배씩 커지게 됩니다!
이제 코드를 보여드리겠습니다.
먼저, $1\leq R\leq 19$ 의 범위에서는 일반적인 binary exponentiation을 이용하여 구하려했습니다.
modulo 의 크기가 $10^{19}$ 인 상황까지 고려하여 unsigned long long을 사용했습니다.
#include <stdio.h>
unsigned long long answer[20];
unsigned long long add_modular (unsigned long long A, unsigned long long B, unsigned long long M);
unsigned long long multiply_modular (unsigned long long A, unsigned long long B, unsigned long long M);
unsigned long long power_modular (unsigned long long X, unsigned long long Y, unsigned long long M);
int main() {
unsigned long long count = 1, r = 1, mod = 10, delta = 4;
while(1) {
unsigned long long result = power_modular (2, r, mod);
unsigned long long temp = result;
int flag_not_1_2 = 0;
while(temp > 0) {
if (((temp % 10) != 1) && ((temp % 10) != 2)) {
flag_not_1_2 = 1;
break;
}
temp /= 10;
if (temp < 10) {
if (temp != 1 && temp != 2) {
flag_not_1_2 = 1;
}
break;
}
}
if (r == 1 || flag_not_1_2) {
if (r == 1) {
answer[count-1] = r;
count += 1;
mod *= 10;
}
r += delta;
}
else {
answer[count-1] = r;
mod *= 10;
delta *= 5;
count += 1;
if (count == 20) {
break;
}
}
}
char string[] = "65539031565589";
int T;
scanf("%d", &T);
for (int i = 0; i < T; i++) {
int R;
scanf("%d", &R);
if (R < 20) {
printf("%llu\n", answer[R-1]);
}
else {
printf("%s\n", string);
}
}
return 0;
}
unsigned long long add_modular (unsigned long long A, unsigned long long B, unsigned long long M) {
A %= M;
B %= M;
if (B >= M - A || A >= M - B) {
return (A - M) + B;
}
else {
return A + B;
}
}
unsigned long long multiply_modular (unsigned long long A, unsigned long long B, unsigned long long M) {
A %= M;
B %= M;
unsigned long long result = 0;
while(B) {
if (B % 2) {
result = add_modular (result, A, M);
}
A = add_modular (A, A, M);
B /= 2;
}
return result;
}
unsigned long long power_modular (unsigned long long X, unsigned long long Y, unsigned long long M) {
if (M > 1000000000ll) {
X %= M;
unsigned long long result = 1;
while (Y) {
if (Y % 2) {
result = multiply_modular (result, X, M);
}
X = multiply_modular (X, X, M);
Y /= 2;
}
return result;
}
else {
X %= M;
unsigned long long result = 1;
while(Y) {
if (Y % 2) {
result = (result * X) % M;
}
X = (X * X) % M;
Y /= 2;
}
return result;
}
}
(C11, 1116KB, 0ms, 제출번호 27747650)
$R=20$ 인 경우, 대회 공식 풀이에서는 스트링을 이용하여 구하는 모습을 보여주었습니다.
(사실 나머지 $R$ 값들에 대해서도 마찬가지로 스트링으로 구했더군요)
공부용으로는 그게 더 바람직하다고는 생각하지만, 이 카테고리에서 다룰 내용은 아닌 것 같습니다.
'분할 정복을 이용한 거듭제곱 > 정수 거듭제곱' 카테고리의 다른 글
| 백준 11693번: n^m 의 약수의 합 (0) | 2021.07.18 |
|---|---|
| 백준 21854번: Monsters (0) | 2021.07.18 |
| 백준 1492번: 합 (0) | 2021.02.19 |
| 백준 15824번: 너 봄에는 캡사이신이 맛있단다 (0) | 2021.02.19 |
| 백준 15710번: xor 게임 (0) | 2021.02.18 |