14934 - 변치 않는 수
본문
임의의 자연수 $n$에 대하여, $00 \cdots 00$ ($0$이 $n$개)에서 $99 \cdots 99$($9$가 $n$개)까지 $10n$개의 수를 생각하자. 이 중에서 원래 수를 제곱한 값의 뒷부분 $n$자리가 원래 수와 똑같은 경우 그 수를 ‘변치 않는 수’라고 하자. 자릿수 $n$이 주어졌을 때 ‘변치 않는 수’는 언제나 $4$가지가 존재한다. 그중 두 개는 $00 \cdots 00$과 $00 \cdots 01$이고, 나머지 두 개 중 하나는 일의 자리 숫자가 $5$이고 다른 하나는 $6$이다. 예를 들어 $n=4$일 때에는 다음 수들이 ‘변치 않는 수’이다.
\[0000^2 = 0000, 0001^2 = 0001, 0625^2 = 390625, 9376^2 = 87909376\]자릿수 $n$이 주어졌을 때, 일의 자리 숫자가 $5$인 ‘변치 않는 수’와 일의 자리 숫자가 $6$인 ‘변치 않는 수’ 중에서 어느 쪽이 더 큰지를 출력하는 프로그램을 작성하는 것이 문제이다.
입력
첫째 줄에 자릿수 $n$이 주어진다. ($1 \leq n \leq 10\,000$)
출력
일의 자리 숫자가 $5$인 ‘변치 않는 수’가 더 크다면 5를, 일의 자리 숫자가 $6$인 ‘변치 않는 수’가 더 크다면 6을 첫째 줄에 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 512MB |
풀이
일단 어떤 수들이 변치 않는 수인지 확인하는 방법으로는 어떤 특정한 수 $x$를 두고 $x^2 \equiv x \pmod{10^l}$인 $x$를 찾으면 될 것이다. 다만 수의 길이는 최대 $10\,000$까지 가능하므로, 모든 수에 대해 $x$를 찾으려면 최대 $10^{10\,000}$개의 수를 모두 고려해야한다. 당연히 불가능할 것이다. 모든 수를 탐색하지 않고 $x$를 특정할 수 있는 방법을 찾아야한다.
그렇다면 수학을 이용하여 후보를 줄여보자. 일단, 10진법이라면 변치 않는 수는 항상 4개 존재한다고 한다. $0$과 $1$은 제외하므로, 2개만 존재한다고 생각하면 된다. 그리고 그 수는 $5$와 $6$이다.
일단 $5$에 대해 예시를 들어가며 규칙이 있나 찾아보자. $a_n$을 “일의 자리가 $5$면서 자릿수가 $n$인 변치 않는 수”라고 정의해보자. 그렇다면 $a_1=5$라고 할 수 있다. 이후 다음을 찾아보자.
- $a_2= 25$ ($25^2 = 625$)
- $a_3= 625$ ($625^2=390625$)
- $a_4 = 0625$ ($0625^2=390625$)
규칙이 보이는가? 모든 $a_n$이 $a_n = c \times 10^l + a_{n-1}$의 꼴을 띠고 있다는 것을 확인할 수 있다. 즉 변치 않는 수의 뒷자리들은 이전의 변치 않는 수와 같다고 할 수 있다. 이 사실이 일의 자리가 $6$인 경우에도 만족하는지 $b_n$을 통해 확인해보자.
- $b_2 = 76$ ($76^2 = 5776$)
- $b_3=376$ ($376^2 = 141376$)
- $b_4 = 9376$ ($9376^2 = 87909376$)
$b_n$도 마찬가지로 $b_n = c \times 10^l + b_{n-1}$의 꼴을 하고 있다! 즉, 이전까지의 변치 않는 수를 계산해두었다면, 가장 앞쪽에 숫자 하나만 추가하여 또 다른 변치 않는 수를 계산할 수 있다. 다만 변치 않는 수는 항상 4개 존재하므로, $c$ 또한 단 1가지만 존재할 수 있다. 이 수에 대해서는 계산을 통해 찾아야 할 것이다. 아래 식을 통해 실마리를 얻어보자.
\[\begin{aligned} {a_n}^2 &\equiv a_n \pmod{10^{l+1}} \\ {a_n}^2 = (c \times 10^l + a_{n-1})^2 &\equiv (c \times 10^l + a_{n-1}) \pmod{10^{l+1}} \\ c^210^{2l} + 2 c a_{n-1} \times{10^l} + {a_{n-1}}^2 &\equiv c \times 10^l + a_{n-1} \pmod{10^{l+1}} \\ 2ca_{n-1} \times{10^l} + {a_{n-1}}^2 &\equiv c \times 10^l + a_{n-1} \pmod{10^{l+1}} \end{aligned}\]즉, 지금까지 $a_{n-1}$를 계산해두었다면, 그 앞에 $c$를 추가하고 검증하는 방법으로 변치 않는 수를 찾아낼 수 있다. 우리는 이전에 ${a_{n-1}}^2 \equiv a_{n-1} \pmod{10^l}$임은 계산했으니, $10^l$ 자릿수만 계산해주면 된다! 우리가 ${a_{n-1}}^2$의 결과를 가지고 있다면, $2ca_{n-1} \times{10^l}$의 결과만 계산하여 합쳐주고 $c$와 같은지 비교하여 답을 찾을 수 있다. 변치 않는 수는 항상 존재하고 답이 유일하므로, 저 답을 만족하는 $c$도 단 1개 존재한다고 가정할 수 있다. 그렇게 $c$를 구했다면, ${a_n}^2$의 값을 업데이트해주어 다음 계산에 활용할 수 있도록 하자.
그러려면 ${a_{n}}^2$의 값을 계산하여 기록할 수 있어야 한다. 일반적으로 만드려는 수 $a_n$은 정수이므로 일반적으로 정수값으로 기록하면 될 것이라고 생각할 수 있지만, 수가 최대 1만자리라는 조건이 있다. 일반적인 자료형으로는 수를 담을 수 없다.
그래서 2만칸짜리 배열을 만들어서, 한 칸에 하나의 자릿수만 가지도록 하였다. arr[i] = 10^i의 자릿수를 나타내도록 말이다. 이후에는 $i$를 1씩 늘려주면서 $c$의 값을 찾고, 그에 따른 ${a_n}^2$을 업데이트해서 가지고 있을 수 있도록 한다. ${a_{n-1}}^2$의 값은 이미 가지고 있으므로, $2ca_{n-1} \times{10^l}$의 값과 $c^210^{2l}$값을 계산해서 넣어주면 된다.
- 참고 알고리즘 : 다이나믹 프로그래밍
코드
사용 언어 : C
최종 수정일 : 2023 / 8 / 7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define MAX_IDX (10000 * 2 + 10)
typedef struct Int {
int digit[MAX_IDX];
} INT;
int n;
INT five, six;
bool isFiveBigger = false;
void init() {
for (int i = 2; i < MAX_IDX; ++i) {
five.digit[i] = 0, six.digit[i] = 0;
}
five.digit[0] = 5, five.digit[1] = 2, five.digit[2] = 6;
six.digit[0] = 6, six.digit[1] = 7, six.digit[2] = 7, six.digit[3] = 5;
return;
}
void solve(int x) {
bool isFiveFound = false, isSixFound = false;
// five
for (int i = 1; i < 10; ++i) {
if ((2 * five.digit[0] * i + five.digit[x]) % 10 == i) {
isFiveFound = true;
int temp;
// 2bi update
for (int j = 0; j < x; ++j) {
five.digit[j + x] += (2 * five.digit[j] * i);
temp = five.digit[j + x] / 10, five.digit[j + x] %= 10, five.digit[j + x + 1] += temp;
}
// i^2 update
five.digit[x * 2] += ((i * i) % 10);
temp = five.digit[x * 2] / 10, five.digit[x * 2] %= 10, five.digit[x * 2 + 1] += temp;
five.digit[x * 2 + 1] += ((i * i) / 10);
temp = five.digit[x * 2 + 1] / 10, five.digit[x * 2 + 1] %= 10, five.digit[x * 2 + 2] += temp;
}
if (isFiveFound == true) {
break;
}
}
if (isFiveFound == false) {
five.digit[x] = 0;
}
// six
for (int i = 1; i < 10; ++i) {
if ((2 * six.digit[0] * i + six.digit[x]) % 10 == i) {
isSixFound = true;
int temp;
// 2bi update
for (int j = 0; j < x; ++j) {
six.digit[j + x] += (2 * six.digit[j] * i);
temp = six.digit[j + x] / 10, six.digit[j + x] %= 10, six.digit[j + x + 1] += temp;
}
// i^2 update
six.digit[x * 2] += ((i * i) % 10);
temp = six.digit[x * 2] / 10, six.digit[x * 2] %= 10, six.digit[x * 2 + 1] += temp;
six.digit[x * 2 + 1] += ((i * i) / 10);
temp = six.digit[x * 2 + 1] / 10, six.digit[x * 2 + 1] %= 10, six.digit[x * 2 + 2] += temp;
}
if (isSixFound == true) {
break;
}
}
if (isSixFound == false) {
six.digit[x] = 0;
}
// compare
if (five.digit[x] > six.digit[x]) {
isFiveBigger = true;
} else if (five.digit[x] < six.digit[x]) {
isFiveBigger = false;
}
return;
}
int main() {
init();
scanf("%d", &n);
for (int i = 2; i < n; ++i) {
solve(i);
}
if (isFiveBigger == true) {
printf("5");
} else {
printf("6");
}
return 0;
}