백준 13171번: A

www.acmicpc.net/problem/13171

13171번: A

---

본문에 Binary Exponentiation의 원리가 잘 설명되어있습니다.

 

$A^{X} \left ( mod \left ( 10^{9} + 7 \right ) \right )$ 을 잘 구해주면 됩니다.

 

다음 링크에 있는 함수만 사용하였습니다.

 

2021/01/23 - [분할 정복을 이용한 거듭제곱] - 기본 이론

기본 이론

 

이때 $10^{9}+7$ 의 크기가 long long의 범위에 비해 상당히 작기 때문에, add_modular 함수는 굳이 사용하지 않았습니다.

 

#include <stdio.h>

long long multiply_modular (long long a, long long b, long long M);
long long power_modular (long long a, long long b, long long M);

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

long long multiply_modular (long long a, long long b, long long M) {
	a %= M;
	b %= M;
	long long result = 0;
	while (b > 0) {
		if (b & 1) {
			result = (result + a) % M;
		}
		a = (a << 1) % M;
		b >>= 1;
	}
	return result;
}

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

 

C11 코드이고, 1116KB, 0ms가 나왔습니다. (번호 25562824)

---

백준에 있는 Binary Exponentiation을 이용하는 문제 중 가장 쉬운 편에 속하는 문제 같습니다.

 

본문에 설명이 잘 되어 있으나 처음 보는 사람한테는 생각하기 어려울 것 같습니다.