BOJ 1629 곱셈

1629번: 곱셈

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

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

 

문제 풀기

간단하게 for문을 사용해서 풀어서 A를B번 곱한 수를 구한다면 int, long long의 범위를 한참 벗어납니다(A와 B는 각각 대략 20억의 수이므로). 따라서 다른 접근방법을 생각해야 합니다.

분할 정복을 사용해야한다.

 

바로 위 이미지 설명을 가지고 이와 같이 구해줄 수 있다.

 

주의 해야할 점 

 

정답 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
long long powCustom(int a, int b, int c)
{
	if (b == 1) return a % c;
	long long val = powCustom(a, b / 2, c);// 계속 반씩 줄여가면서 값을 줄여간다.
    //분할정복
	val = val * val % c;
	//한번에 다 구해서 나머지를 구하는것이 아닌
    // A * A 한번 할때마다 나머지를 RETURN해줌.==>그림설명있음
	if (b % 2 == 0) return val;
	return val * a % c;
    //홀수 일때 ex) 2^5 == 2^4*2 == 2^2*2^2*2이므로 마지막에 a하나 곱해주고 나머지 구해줘야함
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int a, b, c;
	cin >> a >> b >> c;
	cout << powCustom(a, b, c);
}

 

 

글 내용 중에 틀린 것이 있거나 궁금한 것이 있다면 댓글 남겨주세요! 봐주셔서 감사합니다!