[BOJ] 곱셈 1629번 C++

 

 

 

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

접근 방식

 

먼저 A,B,C는 모두 2,147,483,647 이하의 자연수이기 때문에 long long 형을 가져야 한다

또한, B가 매우 크기 때문에 반복문으로 구현하면 시간초과가 발생한다!

 

이를 위해 간단하게 재귀로 풀 수 있다

기저 조건은 B가 1일때까지 B/2로 나눠가며 반환 값을 곱해주면 된다

이때 B가 짝수인지 홀수인지 확인해서

짝수라면 B/2로 재귀를 돌리면 되고

홀수면 B/2의 값에서 A를 한 번 더 곱한 값에서 C를 나눠야 한다

 

이해가 가지 않아도 코드를 보면 쉽게 이해 가능하다!

 

코드

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;

ll sol(ll a, ll b, ll c) {
    if(b == 1) return a % c;
    ll val = sol(a,b/2,c);
    val = val * val % c;
    if(b%2 == 0) return val;
    return val * a % c;

}

int main() {
    ll a,b,c; cin>>a>>b>>c;
    cout<<sol(a,b,c);
}