[ BOJ / C++ ] 1629번 : 곱셈

[ BOJ ] 1629번 : 곱셈

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

---

[  문제  ]

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

[  입력  ]

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

[  출력  ]

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

---

[  문제 접근 및 풀이  ]

A와 B가 모두 2,147,483,647 라면 일반적인 방법으론 분명 시간초과가 뜨기에 풀 수 없다.

중요한 점은 거듭제곱을 분할을 할 수 있는데 식은 다음과 같다.

$a^{b}$ $=$ $a^{b/2}$  * $a^{b/2}$  ( b가 짝수일 경우 )

$a^{b}$ $=$ $a^{b/2}$  * $a^{b/2 +1}$  ( b가 홀수일 경우 )

이 두 경우를 나누어서 재귀로 풀 수 있다면 $A^{B}$%$C$도 빠르게 구할 수 있다.

연산 과정에서 overflow가 나타날 수 있기 때문에 long long으로 형을 선언해서

int의 최댓값을 서로 곱해도 커버가 가능하다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
void Q_1629();
long long mod(long long a, long long b, long long c);
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_1629();
}
void Q_1629(){
    long long a,b,c;
    cin >> a >> b >> c;
    cout << mod(a,b,c);
}
long long mod(long long a, long long b, long long c){
    if (b==1) return a%c;
    long long value= mod(a,b/2,c);
    value= (value*value)%c;
    if(b%2==0) return value;
    return (value*a) %c;
}

---