알고리즘
[C++] Boj 1629 곱셈
(ꐦ •᷄ࡇ•᷅)
2025. 1. 7. 12:23
문제 링크
[1629 곱셈]
접근
그냥 무턱대고 그대로 구현하면 맞힐 수 없다. 따라서 나머지 연산의 특징을 잘 이해해야 한다. 나는 감이 안 잡혀서 풀이를 따라 하면서 이해했다.
풀이 참고
나머지 연산의 특징
1. a와 b의 표현식
a = q1 * m + r1
b = q2 * m + r2
- a와 b를 나눗셈의 몫(q1, q2)과 나머지(r1, r2)로 나타낸 것이다.
- q1과 q2는 정수 몫이다.
- r1과 r2는 a mod m, b mod m으로 정의된 나머지이다.
- 즉, r1 = a % m이고, r2 = b % m이다.
2. a * b를 전개
두 수 a와 b를 곱해보면 다음과 같다:
a * b = (q1 * m + r1) * (q2 * m + r2)
이걸 전개하면
a * b = (q1 * q2 * m^2) + (q1 * r2 * m) + (q2 * r1 * m) + (r1 * r2)
3. a * b mod m를 구하기
이제 a * b를 m으로 나눈 나머지를 구한다. 여기서 중요한 점은 나머지 연산의 성질이다:
- 모듈러 연산 성질
- k * m mod m = 0 (어떤 정수 k라도 m의 배수는 mod m에서 0이 된다).
위 성질을 사용하여 (q1 * q2 * m^2)와 (q1 * r2 * m) 및 (q2 * r1 * m)가 mod m에서 사라진다.
a * b mod m = (r1 * r2) mod m
즉, a * b를 m으로 나눈 나머지는 (r1 * r2)를 m으로 나눈 나머지와 같다.
4. r1과 r2의 정의 대입
앞에서 r1 = a mod m이고 r2 = b mod m이라고 했으므로
r1 * r2 mod m = (a mod m) * (b mod m) mod m
따라서 최종적으로
a * b mod m = (a mod m * b mod m) mod m
결론
- a와 b를 몫과 나머지로 나눈다.
- 곱한 뒤 m으로 나눈 나머지는 곱셈의 나머지를 이용해 구할 수 있다.
- 이는 나머지 연산의 성질을 활용한 결과이며, 최종 식은
- a * b mod m = (a mod m * b mod m) mod m
- 이 성질은 모듈러 산술에서 매우 중요한 법칙으로, 큰 수의 연산을 효율적으로 처리하는 데 사용된다.
예시
다음 예시를 적용해 보자. (12^58 mod 67 = 4이다.)
1. 문제의 핵심: 거듭제곱 계산의 단순화
- 12^58 mod 67 = 4라는 사실이 주어졌다.
- 즉, 12^58을 67로 나누면 나머지가 4이다.
- 이 정보를 이용하면 더 큰 거듭제곱, 즉 12^116 mod 67을 간단히 계산할 수 있다.
2. 거듭제곱의 분할
12^116은 거듭제곱의 성질에 의해 다음과 같이 분해할 수 있다:
12^116 = (12^58) × (12^58)
따라서
12^116 mod 67 = [(12^58 mod 67) × (12^58 mod 67)] mod 67
3. 주어진 조건 대입
- 12^58 mod 67 = 4라고 했으므로, 이를 대입하면
12^116 mod 67 = (4 × 4) mod 67
이제 계산하면
4 × 4 = 16
따라서
12^116 mod 67 = 16
코드
#include <iostream>
using namespace std;
using ull = unsigned long long;
// A ^ B % C
// A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
// A^B mod C = (A^B/2 mod C)^2 mod C
ull Solve(ull a, ull b, ull c)
{
if (b == 1) return a % c;
ull val = Solve(a, b / 2, c);
val = val * val % c;
// b가 짝수일 때
// 중간 과정 반환
if (b % 2 == 0) return val;
// b가 홀수일 때
// (a^b) % c = [(a^(b-1)) × a] % c
// = (val × a) % c
return val * a % c;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ull A, B, C;
cin >> A >> B >> C;
cout << Solve(A, B, C);
return 0;
}