[백준] 1629. 곱셈 풀이

https://www.acmicpc.net/problem/1629

 

a^b = a*a*a...

a들을 반씩 나누어서 계산 후 c로 나눠가며 나머지를 구하는 함수(b==1 -> a%c)
-> 재귀
결과 출력

 

---

C

더보기

#include <stdio.h>

long long multiple(long long a, long long b, long long c){
    long long v = 1;
    if(b == 1) return a % c;
    else if(b % 2 == 0){
        long long t = multiple(a, b / 2, c);
        v *= t; v %= c;
        v *= t; v %= c;
    }
    else{
        v *= multiple(a, b / 2, c); v %= c;
        v *= multiple(a, (b / 2) + (b % 2), c); v %= c;
    }
    return v;
}

int main() {
    long long a, b, c;
    long long res;
    scanf("%lld %lld %lld", &a, &b, &c);
    res = multiple(a, b, c);
    printf("%lld", res);
}

---

Python

더보기

def multiple(a, b, c):
    v = 1
    if b == 1: return a % c
    elif b % 2 == 0:
        t = multiple(a, b//2, c)
        v *= t; v %= c
        v *= t; v %= c
    else:
        v *= multiple(a, b // 2, c); v %= c
        v *= multiple(a, (b // 2) + (b % 2), c); v %= c
    return v

a, b, c = map(int, input().split())
res = multiple(a, b, c)
print(res)