(SWEA) 24397번 - 거듭제곱 후 나누기
(SWEA) 24397번 - 거듭제곱 후 나누기
문제
풀이
거듭제곱 - 분할 정복
모든 십진수는 이진수로 표현 가능하다. 이진수로 표현 가능하다는 것은 2의 거듭제곱의 합으로 나타낼 수 있다는 것이다. 예를 들어 $13$은 $1101_2 = 2^3+2^2+2^0$로 나타낼 수 있다. 이러한 성질을 바탕으로 어떤 수의 거듭제곱은 지수가 2의 거듭제곱인 수들의 합으로 표현할 수 있다. 예를 들어 $3^{13}=3^8+3^4+3^1$로 표현 가능하다.
위 내용을 바탕으로 분할 정복하며 어떠한 수의 거듭제곱을 구할 수 있다.
소수점 앞, 뒤 3자리 구하기
$X^Y$를 $Z$로 나눈 몫을 $Q$, 나머지를 $R$이라고 할 때, $X^Y=Q \cdot Z+R$라고 표현할 수 있다.
먼저 소수점 뒤 3자리는 나머지에 의해 결정된다. 실제 소수점 아래 부분은 $X^Z (mod\ Z)$이고, 우리가 원하는 부분은 소수점 뒤 3자리 이므로 1000을 곱한다. 즉, (x^y % z) * 1000 / z으로 구할 수 있다.
소수점 앞 3자리는 몫에 의해 결정된다. 마지막 3자리는 $Q(mod\ 1000)$이다.
$Q$의 마지막 3자리를 $q_{end}$, 그 앞의 수를 $q_{high}$라고 하자. 그렇다면 $Q=1000 \cdot q_{high}+q_{end}$이다. 이를 원래 식에 대입하면 다음과 같다.
\[\begin{aligned} X^Y &= (1000 \times q_{high} + q_{end}) \times Z + R \\ &= (1000 \times q_{high} \times Z) + (q_{end} \times Z) + R \\ &= (q_{high} \times 1000Z) + (q_{end} \times Z + R) \end{aligned}\]이제 양변을 $1000Z$로 나머지를 구해보자.
\[X^Y \pmod{1000Z} = q_{end} \times Z + R\]위 식을 $Z$로 나누면 $q_{end}$만 남게된다. $R<Z$이므로 정수 나눗셈에서 $R$은 사라진다.
정리하면, 소수점 앞 3자리는 (x^y % 1000z) / z로 구할 수 있다.
소수점 앞 숫자 자리수 판별
소수점 앞의 숫자가 2자리 이하면 앞에 0을 붙여 출력해야 한다. 소수점 앞 숫자의 자리수는 어떻게 판별해야 할까?
\[\frac{X^Y}{Z} \ge 1000\]위 수식을 만족하는 경우 소수점 앞의 수가 3자리 이상이라는 뜻이다. 즉, $X^Y$가 $1000Z$ 미만이면 앞에 0을 붙여 출력해야 한다.
코드
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
#include <iostream>
using namespace std;
long long divconq(long long x, long long r, long long z) {
long long ret = 1;
x %= z;
while (r > 0) {
if (r % 2 == 1)
ret = (ret * x) % z;
x = (x * x) % z;
r /= 2;
}
return ret;
}
int main() {
int T;
cin >> T;
while (T--) {
long long x, y, z;
cin >> x >> y >> z;
// 소수점 앞 3자리: (x^y % 1000z) / z
// 소수점 뒤 3자리: (x^y % z) * 1000 / z
long long int_part = divconq(x, y, 1000 * z) / z;
long long frac_part = divconq(x, y, z) * 1000 / z;
bool is_large = false;
if (x == 1) {
is_large = false;
}
// 2^30 > 10^9
else if (y >= 30) {
is_large = true;
}
else {
long long tmp = 1;
long long limit = 1000 * z;
bool overflow = false;
for (int i = 0; i < y; i++) {
tmp *= x;
if (tmp >= limit) {
overflow = true;
break;
}
}
is_large = overflow;
}
if (is_large) {
printf("%03lld.%03lld\n", int_part, frac_part);
}
else {
printf("%lld.%03lld\n", int_part, frac_part);
}
}
}
데이터 타입은 int 대신 long long을 사용해야 한다. 곱하는 과정에서 오버플로우가 발생할 수 있기 때문이다.
시간복잡도
분할 정복 과정에서 시간복잡도는 $O(logY)$이다. 매 반복마다 지수가 2로 나누어지는데, $r$의 비트 수만큼 반복되기 때문이다.
공간복잡도
분할 정복 함수가 반복문으로 구현되어 있고, 정해진 변수만 사용하므로 공간복잡도는 $O(1)$이다.