[백준] 1629번 : 곱셈 (C++)

1629번 : 곱셈

---

문제 )

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

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

#include <iostream>
 
using namespace std;
 
int a, b, c;
 
// 분할 정복
long long recur(int a, int b, int c)
{
    if (b == 0)
    {
        return 1;
    }
    if (b == 1)
    {
        return a % c;
    }
    
    long long temp = recur(a, b / 2, c);
 
    if (b % 2 == 0)
    {
        return temp * temp % c;
    }
    else
    {
        return a * (temp * temp % c) % c;
    }
}
 
int main()
{
    cin >> a >> b >> c;
    cout << recur(a, b, c);
 
    return 0;
}
 

 

---

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

1629번: 곱셈