11030 - SUPER HATS
본문
양의 정수 $a, b$에 대해서, $a$의 $b$ 초지수승은 $a ↑↑ b$와 같이 나타낸다. 초지수승의 정의는 다음과 같다.
\[a ↑↑ 1 = a\] \[a ↑↑ (k + 1) = a ^ {(a ↑↑ k)}\]따라서 예를 들면, $3↑↑2 = 3^3 = 27$ 이고, $3↑↑3 = 3^{27} = 7625597484987$이다.
$a ↑↑ b$의 마지막 8자리를 출력하세요.
입력
양의 정수 $a, b$가 입력된다. ($a, b \leq 20000$)
출력
$a ↑↑ b$의 마지막 8자리를 출력하시오.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 256MB |
풀이
초지수승 (Tetration) 자체가 power tower의 case 중 하나이다. 이전에 “N과 M” 문제와 비슷하게, $a$를 반복해서 제곱한다. 이전 문제에서 보다시피 빠른 시간 내에 특정 값으로 수렴함은 알고 있기 때문에 그대로 계산하면 된다. 심지어 숫자들 중 마지막 8자리만 출력하라고 했으므로 mod 값을 1억으로 주면 된다는 것도 알 수 있다. 결국 power tower 문제로 생각할 수 있다.
그래서, power tower만 확실하게 계산할 수 있는 방법만 가지고 있다면 답을 얻을 수 있다. 이전에 power tower를 계산했던 문제에서 코드를 가져왔다. main 함수를 제외하고는 전부 다. power tower 자체에 관한 설명은 ‘참고 알고리즘’을 참고하도록 하자.
문제는 출력 부분이다. 이 부분 때문에 5번이나 굴렀다. 8자리만 출력해야하는데, 모듈러만 취한다고 되는 것이 아니었다. 극단적인 예시로 $20000, 20000$이라는 입력을 주었을 때, 결과값이 $0$이었다. 하지만 저 숫자는 분명히 1억을 넘으므로 $00000000$이 출력되어야한다. 즉 출력부분을 %08lld로 해주어야한다는 의미이다.
그렇다고 무조건 저 방식으로 출력하면 안된다! 그 예시로 $2, 2$가 있다. 이 경우 답은 $4$인데, 이 숫자는 그 자체가 한자리밖에 되지 않으므로 $00000004$가 아니라 $4$라고만 출력해야한다. 그래서 %08lld%도 막 써서는 안된다!
처음에는 계산 중에 1억을 넘는 경우를 찾아 묶어내려고 하였는데 계속해서 실패했다. 그래서 그냥 1억이 넘지 않는 case들을 손수 계산해서 분기문으로 처리해버렸다. 좀 귀찮긴 해도 확실한 방법으로 말이다.
뭐 어때.. 성공했으면 되는거지..
- 참고 알고리즘 : Power Tower
코드
사용 언어 : C
최종 수정일 : 2023 / 3 / 11
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include <stdio.h>
typedef long long ll;
#define MAX_IDX (int)(20000 + 3)
ll arr[MAX_IDX];
ll phi(ll x) {
ll retval = 1;
for (ll i = 2; i * i <= x; ++i) {
ll k = 0;
ll p = 1;
while (x % i == 0) {
++k, p *= i;
x /= i;
}
if (k > 0) {
p /= i;
retval *= (p * (i - 1));
}
}
if (x > 1) {
retval *= (x - 1);
}
return retval;
}
ll gcd(ll a, ll b) {
ll temp = 0;
while (b != 0) {
temp = a % b;
a = b;
b = temp;
}
return a;
}
ll inverse(ll a, ll m) {
ll m0 = m;
ll y = 0;
ll x = 1;
if (m == 1) {
return 0;
}
while (a > 1) {
ll q = a / m;
ll t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) {
x = x + m0;
}
return x;
}
ll chineseRemainder(ll mod, ll pe, ll r) { return ((mod / pe) * (inverse(mod / pe, pe) * r)); }
ll powWithModulo(ll x, ll y, ll mod) {
ll ret = 0;
if (y == 0) {
return 1;
} else if (y == 1) {
ret = x;
} else {
ll xx = powWithModulo(x, y / 2, mod);
if (y % 2 == 0) {
ret = xx * xx;
} else {
ret = (xx * xx % mod) * x;
}
}
return ret % mod;
}
#define INF 31
ll powUntilMax(ll x, ll y) {
ll ret = 0;
if (y == 0) {
return 1;
} else if (y == 1) {
ret = x;
} else {
ll xx = powUntilMax(x, y / 2);
if (xx >= INF) {
return INF;
}
if (y % 2 == 0) {
ret = xx * xx;
} else {
ret = (xx * xx) * x;
}
}
return ret;
}
ll getPower(ll s, ll e, ll cur) {
if (s == e) {
return 0;
} else if (s + 1 == e) {
return powUntilMax(arr[s], cur);
}
if (cur >= INF) {
return INF;
} else if (arr[s] >= INF) {
return INF;
} else if (arr[e - 1] >= INF) {
return INF;
}
return getPower(s, e - 1, powUntilMax(arr[e - 1], cur));
}
ll solve(ll s, ll e, ll mod) {
if (mod == 1) {
return 0;
} else if (arr[s] == 1) {
return 1;
} else if (s + 1 == e) {
return arr[s] % mod;
}
if (gcd(arr[s], mod) == 1) {
return powWithModulo(arr[s], solve(s + 1, e, phi(mod)), mod);
}
// ai and mod is not coprime
// loop for mod's prime set -> chinese remainder theorem
ll subMod = mod;
ll ret = 0;
for (ll i = 2; i * i <= subMod; ++i) {
ll cnt = 0;
ll pe = 1;
while (subMod % i == 0) {
++cnt, pe *= i;
subMod /= i;
}
if (cnt > 0) {
if (gcd(arr[s], i) == 1) {
ret += chineseRemainder(mod, pe, powWithModulo(arr[s], solve(s + 1, e, phi(pe)), pe));
} else {
ll powerValue = getPower(s + 1, e, 1);
if (powerValue < cnt) {
ret += chineseRemainder(mod, pe, powWithModulo(arr[s], powerValue, pe));
}
}
}
}
if (subMod > 1) {
ll cnt = 1, pe = subMod;
if (gcd(arr[s], subMod) == 1) {
ret += chineseRemainder(mod, pe, powWithModulo(arr[s], solve(s + 1, e, phi(pe)), pe));
}
}
return ret % mod;
}
ll main() {
ll a, b;
scanf("%lld %lld", &a, &b);
for (int i = 0; i < b; ++i) {
arr[i] = a;
}
#define STD (ll)(1e8)
ll ans = solve(0, b, STD);
// printf("ans : %lld\n", ans);
if (a == 1) {
printf("%lld", ans);
} else if (a == 2) {
if (b > 4) {
printf("%08lld", ans);
} else {
printf("%lld", ans);
}
} else if (b == 1) {
printf("%lld", ans);
} else if (b == 2) {
if (a < 9) {
printf("%lld", ans);
} else {
printf("%08lld", ans);
}
} else {
printf("%08lld", ans);
}
return 0;
}