[C++] Boj 1629 곱셈

문제 링크

[1629 곱셈]

접근

그냥 무턱대고 그대로 구현하면 맞힐 수 없다. 따라서 나머지 연산의 특징을 잘 이해해야 한다. 나는 감이 안 잡혀서 풀이를 따라 하면서 이해했다.

풀이 참고

[실전 알고리즘] 0x0B강 - 재귀

나머지 연산의 특징

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

---

결론

1. a와 b를 몫과 나머지로 나눈다.
2. 곱한 뒤 m으로 나눈 나머지는 곱셈의 나머지를 이용해 구할 수 있다.
3. 이는 나머지 연산의 성질을 활용한 결과이며, 최종 식은
4. a * b mod m = (a mod m * b mod m) mod m
5. 이 성질은 모듈러 산술에서 매우 중요한 법칙으로, 큰 수의 연산을 효율적으로 처리하는 데 사용된다.

예시

다음 예시를 적용해 보자. (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;
}