BOJ - 1629번_곱셈

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

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


풀이

AB mod C = (A mod C * B mod C) mod C 로 계산할 수 있다.

B가 짝수면 val 값을 그대로 반환하고, 홀수면 A를 한번 더 곱한 값을 반환한다.


소스코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll A, B, C;
	cin >> A >> B >> C;
	
	cout << pow(A,B,C);
}