목차
백준 1629번 곱셈
출처: https://www.acmicpc.net/problem/1629
1. 문제
2. 입력
$2,147,483,647 = 2^{31}-1$ 즉, $1 \le A, B, C \le 2^{31}-1$
3. 출력
4. 예제
5. 풀이
5.1. 시간초과
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
// 입력
int A, B, C, ans;
st = new StringTokenizer(br.readLine());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
ans = A;
// 계산
for (int i = 0; i < B; i++) {
ans = ans * A % C;
}
// 출력
sb.append(ans);
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
5.2. Overflow
-
고속 거듭제곱 \(A^k = \begin{cases} A^{\frac{k}{2}} \, A^{\frac{k}{2}}, & \text{if } k \text{ is even},\\[4pt] A^{\frac{k-1}{2}} \, A^{\frac{k-1}{2}} \, A, & \text{if } k \text{ is odd}. \end{cases}\) \(\begin{align} 2^{17} &= 2^8 \times 2^8 \times 2 \\ &= (2^4)^2 \times (2^4)^2 \times 2 \\ &= ((2^2)^2)^2 \times ((2^2)^2)^2 \times 2 \\ &= (((2^1)^2)^2)^2 \times (((2^1)^2)^2)^2 \times 2 \\ \end{align}\)
-
모듈러 연산의 성질 곱셈: $(a×b)(mod \; n)=((a(mod \; n))×(b(mod \; n)))(mod \; n)$ 지수: $(a^b)(mod \; n)=((a(mod \; n))^b)(mod \; n)$
\(\begin{align} 2^{17} \; mod \; 7 &= 131,072 \; mod \; 7 = 4 \\ &= (((2^8 \; mod \; 7)^2 \; mod \; 7) \times 2) \; mod \; 7 \\ &= ((((2^4 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7) \times 2) \; mod \; 7 \\ &= (((((2^2 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7) \times 2) \; mod \; 7 \\ &= ((((((2^1 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7) \times 2) \; mod \; 7 \\ \end{align}\) \(\begin{align} 2^{17} \; mod \; 7 &= 131,072 \; mod \; 7 = 4 \\ &= ((((((2^1 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7) \times 2) \; mod \; 7 \\ &= ((((((2)^2 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7) \times 2) \; mod \; 7 \\ &= (((((4)^2 \; mod \; 7)^2 \; mod \; 7)^2 \; mod \; 7) \times 2) \; mod \; 7 \\ &= ((((2)^2 \; mod \; 7)^2 \; mod \; 7) \times 2) \; mod \; 7 \\ &= (((4)^2 \; mod \; 7) \times 2) \; mod \; 7 \\ &= ((2) \times 2) \; mod \; 7 \\ &= 4 \\ \end{align}\)
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int solve(int A, int B, int C) {
int ans = 1;
while (B > 0) {
if (B%2 == 1) { // 홀수일 때
ans = ans * A % C; // <- Overflow
}
A = A * A % C; // <- Overflow
B /= 2;
}
return ans % C;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
// 입력
int A, B, C;
st = new StringTokenizer(br.readLine());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
// 계산
int ans = solve(A, B, C);
// 출력
sb.append(ans);
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
3. 정답
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static long solve(long A, long B, long C) {
long ans = 1;
while (B > 0) {
if (B%2 == 1) { // 홀수일 때
ans = (ans * A % C);
}
A = (A * A % C);
B /= 2;
}
return ans % C;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
// 입력
long A, B, C;
st = new StringTokenizer(br.readLine());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
// 계산
long ans = solve(A, B, C);
// 출력
sb.append(ans);
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
Comments