[백준 c++] 1629 곱셈

문제 설명

https://www.acmicpc.net/problem/1629
자연수 A를 B번 곱한 수를 C로 나눈 값을 구하는 문제다.
A, B, C는 모두 2,147,483,647 이하의 자연수다.

아이디어

1차 시도 -for문

처음에 그냥 엄청나게 커지는 수를 막기 위해(A*A*A*A)%C의 값이 (A%C*A%C*A%C*A%C)의 값과 똑같다는 것을 이용해서 for문으로 풀었는데
시간초과가 났다.(0.5초로 제한)

2차 시도 -재귀함수

거듭제곱은 분할해서 나타낼 수 있다는 것을 이용해서 풀 수 있었다.
3^4=3^2*3^2 , 3^2=3*3
이 경우 3^4를 계산하기위해 3, 3^2만 계산하면 되기 때문에 시간을 줄일 수 있다.

만약 b가 홀수라면 3^4까지 계산한 후에 한 번 더 a을 곱해주고 c로 나눠주면된다.

전체 코드

#include <iostream>
using namespace std;
typedef long long ll;
ll a, b, c;
ll mul(ll a, ll b)
{
    if (b == 1)
        return a % c;
    ll ret = mul(a, b / 2);
    //재귀함수 다 호출한 이후(거꾸로 돌아갈 때)
    
    ret = (ret * ret) % c;
    if (b % 2)
        ret = (ret * a) % c; //홀수면 한 번 더 곱해준 뒤 나머지 연산
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> b >> c;
    cout << mul(a, b) << "\n";
}