백준 11819번: The Shortest does not Mean the Simplest

www.acmicpc.net/problem/11819

11819번: The Shortest does not Mean the Simplest

---

이전에 올렸던 1629, 13171번과 거의 같은 문제입니다.

2021/01/23 - [분할 정복을 이용한 거듭제곱/정수 거듭제곱] - 백준 1629번: 곱셈

2021/01/23 - [분할 정복을 이용한 거듭제곱/정수 거듭제곱] - 백준 13171번: A

 

따라서 코드도 거의 같습니다.

 

#include <stdio.h>

long long add_modular (long long x, long long y, long long M);
long long multiply_modular (long long x, long long y, long long M);
long long power_modular (long long x, long long y, long long M);

int main() {
	long long A, B, C;
	scanf("%lld %lld %lld", &A, &B, &C);
	printf("%lld", power_modular(A, B, C));
	return 0;
}

long long add_modular (long long x, long long y, long long M) {
	x %= M;
	y %= M;
	if (x >= M - y || y >= M - x) {
		return (x - M) + y;
	}
	else {
		return x + y;
	}
}

long long multiply_modular (long long x, long long y, long long M) {
	x %= M;
	y %= M;
	long long temp = x;
	long long result = 0;
	while (y > 0) {
		if (y & 1) {
			result = add_modular (result, temp, M);
		}
		temp = add_modular (temp, temp, M);
		y >>= 1;
	}
	return result;
}

long long power_modular (long long x, long long y, long long M) {
	x %= M;
	long long temp = x;
	long long result = 1;
	while (y > 0) {
		if (y & 1) {
			result = multiply_modular (result, temp, M);
		}
		temp = multiply_modular (temp, temp, M);
		y >>= 1;
	}
	return result;
}

 

C11 , 1116KB, 0ms입니다. (제출번호 25518391)

---

이 문제는 특이하게도 2009년, International Zhautykov Olympiad의 D번으로 출제된 문제라고 합니다.

 

그래서 그런지, 아니면 그냥 언어가 영어라서 그런지, 제가 이 글을 쓴 시점에서 정답자가 겨우 66명에 불과했습니다.