[백준] 1629번: 곱셈

Solved.ac 실버1
https://www.acmicpc.net/problem/1629

설명

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

입력

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

출력

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

해결 Tip

알고리즘 분류

• 수학
• 분할 정복을 이용한 거듭제곱

모듈러(나머지) 연산 분배법칙 :

• (A+B) % C = (A%C + B%C) %C
• (A - B) % C = (A%C - B%C) %C
• (AB) % C = (A%C B%C) %C

거듭제곱 법칙 :

• A^(n+m) = A^n * A^m

코드

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int A, B, C, ans;

int solve(int k) {
    if (k == 1) return A % C;
    
    long long int n = solve(k/2) % C;

    if (k % 2) return (((n*n) % C)*A) % C;
    else return (n*n) % C;
}

int main() {
    fastio;
    cin >> A >> B >> C;
    cout << solve(B);
	return 0;
}