Lee's Programming Practice

알고리즘 문제 풀이

문제

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

풀이

단순한 곱셉 문제처럼 보이지만 실상은 그렇지 않다.

1. O(n)의 시간복잡도로 생각해도 B의 범위가 20억이 넘어 시간제한에 걸린다.

2. int 자료형의 범위를 훨씬 넘어간다

따라서 long long 자료형을 사용하고 시간제한은 분할정복과 재귀호출의 방식을 사용했다.

소스 코드

#define _CRT_SECURE_NO_WARNINGS
// 헤더파일
#define ll long long int
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <cctype>
#include <set>
#include <string.h>

using namespace std;
ll A, B, C;

ll mul(ll A, ll B, ll C) {
	if (B == 1)
		return A;
	else {
		ll temp = mul(A, B / 2, C);

		if (B % 2) {
			return ((temp * temp) % C * A) % C;
		}
		else
			return (temp * temp) % C;
	}
}

int main() { 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> A >> B >> C;

	cout << mul(A % C, B, C) << '\n';
}