백준 s1 1629 곱셈 c++

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

1629번: 곱셈

 

풀이

시간 제한이 0.5초라 그냥 a*func(a-1)은 시간 초과가 걸릴 수 있다.

 

A^B % C = A^(B/2) % C * A^(B/2) % C로 나뉘어질 수 있고 이렇게 하면 log 시간 복잡도가 되기 때문에 괜찮아 보인다.

 

수도 코드

func (a, b, c)
	if (b == 1) return a % c
    else return func(a, b/2, c)^2

 

 

코드

/*boj s1 1629 곱셈*/
#include <iostream>
#define MAXN 105
using namespace std;

int A, B, C;

long long func(int a, int b, int c) {
    if (b == 1)
        return a % c;
    else {
        long long res = func(a, b / 2, c);

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

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> A >> B >> C;

    cout << func(A, B, C) << "\n";
}

 

 

실수했던 점

 

수정 전

        if (b % 2 == 0)
            return res * res % c;
        else
            return a * res * res % c;

 

수정 후

        res = res * res % c;
        if (b % 2 == 0)
            return res % c;
        else
            return a * res % c;

 

아무리 long long이라고 해도 overflow가 났나보다