[백준 1629] 곱셈 (C++/Python)

* 모듈러 연산
(a * b) % n = ((a % n) * (b % n)) % n

 

문제에서 제시한 예시를 풀어서 설명하자면

10^11 % 12 = (10 * 10^5 * 10^5) % 12 = ( (10 % 12) * (10^5 % 12) * (10^5 % 12 ) ) % 12

= ( (10 % 12) * ((10 * 10^2 * 10^2) % 12) * ((10 * 10^2 * 10^2) % 12)) ) % 12

= ( (10 % 12) * ( (10%12) * (10^2 % 12) * (10^2 % 12) % 12 ) * ( (10%12 ) * (10^2 % 12) * (10^2 % 12) % 12 ) ) % 12

= ( (10 % 12) * ( (10%12) * ((10*10) % 12) * ((10*10) % 12) % 12) * ( (10%12) * (10^2 % 12) * (10^2 % 12) % 12) ) % 12

= ... * ( (10%12) * ( ((10%12) * (10%12))%12 ) * ( ((10%12) * (10%12)) % 12) * ...

이렇게 풀 수 있다.

---

 

 

C++)

#include <iostream>
using namespace std;

int calc(long long a, long long b, long long c) {
    if (b == 1)
        return a % c;

    long long temp = calc(a, b / 2, c);
    temp = temp * temp % c;

    if (b % 2 == 0)
        return temp;
    return temp * a % c;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, c;
    cin >> a >> b >> c;

    cout << calc(a, b, c);

    return 0;
}

 

 

 

Python)

import sys

a, b, c = map(int, sys.stdin.readline().rstrip().split())

def calc(a, b, c):
    if b == 1:
        return a%c
    temp = calc(a, b//2, c)
    temp = temp * temp % c

    if b%2 == 0:
        return temp
    return temp * a % c

print(calc(a,b,c))