BOJ [1629] 곱셈

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

1. 분류

수학, 분할정복

2. 풀이

A를 B만큼 제곱한 수를 C로 나누어 나머지를 구하는 문제이다.

입력 범위가 int 한계치(2^32 - 1)기 때문에 자료형은 unsigned long long형으로 잡았다.

입력 한계치가 매우 큰 만큼 B번 거듭제곱할 때 O(N)으로 구하면 무조건 시간 초과가 나게 된다.

B를 반씩 나누어가며 분할정복으로 거듭제곱을 구하면 시간 내에 풀 수 있다.

3. 소스코드

#include <cstdio>

typedef unsigned long long ull;

ull power(ull x, ull y, ull div)
{
	ull res = 1LL;

	while (y)
	{
		if (y & 1)
		{
			res *= x;
			res %= div;
		}
		x *= x;
		x %= div;
		y /= 2LL;
	}

	return res;
}

int main()
{
	ull a, b, c;
	scanf("%llu %llu %llu", &a, &b, &c);

	printf("%llu\n", power(a, b, c));

	return 0;
}