[백준] 1629_곱셈

[문제]: 1629번: 곱셈 (acmicpc.net)

 

A, B, C가 int보다 작은 자연수라 하더라도, 곱하기 연산을 하는 과정에서 int의 범위(약 21억)보다 커질 수 있다. 따라서 long long 자료형을 사용한 것을 확인 할 수 있다. POWER() 함수의 기저 사례(base case)는 지수 b가 1일 때 자기 자신(a)을 반환한다. 또한,

\[a\equiv b\pmod{m} \text{이고 } c\equiv d\pmod{m} \text{이면, } ac\equiv bd\pmod{m} \text{이다.}\]

예를 들어,

\[12^{58}\equiv 4\pmod{67}\text{이면 위 식에 의해, } 12^{116}\equiv 16\pmod{67}\text{이다.}\]

\(12^{116}\)을 67로 나눈 나머지 16은, \(12^{58}\)을 67로 나눈 나머지인 4로 구할 수 있다는 것이다. 따라서\(a^{b}\pmod m\)을 구하기 위해서 \(a^{b/2}\pmod m\)을 먼저 구하면 된다. 정수형 데이터 타입에서의 나눗셈의 몫은 버림이 생기므로, b가 홀수일 경우 한번 더 a를 곱해줘야 한다. 

#include <iostream>
using namespace std;
using ll = long long;

ll A, B, C;
ll POWER(ll a, ll b, ll c)
{
	if (b == 1) return a % c;
	ll ret = POWER(a, b / 2, c);
	ret = ret * ret % c;
	if (b % 2 == 0) return ret;
	return ret * a % c;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> A >> B >> C;
	cout << POWER(A, B, C);
	return 0;
}