백준 27299번: 헌내기 현철

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

27299번: 헌내기 현철

---

구해야 하는 값은 $A^{B^{C}}$를 $10^{7}$으로 나눈 나머지입니다. 여기까지는 생각하기 매우 쉽지만, $C$의 범위가 매우 큽니다.

 

Euler's Theorem을 반복하여 적용할 수 있지만, 저는 그냥 한 번만 적용하고 끝내는 게 더 편할 수도 있다는 생각을 했습니다. 왜냐하면 17315번 에서 이미 한 번 구현했기 때문입니다 ㅎㅎ..

 

주의할 점은 엣지 케이스인데,

$$A^{B^{C}} \equiv A^{ B^{C} \; \textrm{mod} \; 10^{7} + \phi (10^{7}) } \; \textrm{mod} \; 10^{7}$$

가

$$B^{C} \geq \log_{2} (10^{7}) \approx 24$$

에서 성립한다는 것입니다. 저는 안전하게 $B^{C}$가 27 이상일 때 Euler's Theorem을 쓰기로 했습니다.

 

따라서 제 코드는 다음과 같습니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

typedef unsigned long long ull;

#define mod 10000000ull
#define phimod 4000000ull

bool is_B_to_C_small_than_27 (ull B, char* C, int L);

ull power (ull x, ull y);
ull power_modular_mod (ull x, ull y);
ull power_modular_phimod (ull x, ull y);
ull power_modular_phimod_log10 (ull x, char* P, int L);

int main() {
	
	int T;
	scanf("%d", &T);
	while(T--) {
		ull A, B, i;
		char C[1001];
		scanf("%llu %llu %llu %s", &A, &B, &i, C);
		
		if (B == 1) {
			printf("%llu\n", A % mod);
		}
		else {
			int lenC = strlen(C);
			if (is_B_to_C_small_than_27(B, C, lenC)) {
				ull B_to_the_power_of_C = power(B, atoi(C));
				ull remainder = power_modular_mod (A, B_to_the_power_of_C);
                printf("%lld\n", (remainder / power(10, i)) % 10);
			}
			else {
				ull B_to_the_power_of_C_phimod = power_modular_phimod_log10(B, C, lenC);
				ull remainder = power_modular_mod (A, B_to_the_power_of_C_phimod + phimod);
                printf("%lld\n", (remainder / power(10, i)) % 10);
			}
		}
	}
	return 0;
}

bool is_B_to_C_small_than_27 (ull B, char* C, int L) {
	// return true if B^C < 27
	if (B >= 27 || L >= 2) {
		return false;
	}
	else if (B >= 6 && C[0] >= '2') {
		return false;
	}
	else if (B >= 3 && C[0] >= '3') {
		return false;
	}
	else if (B >= 2 && C[0] >= '5') {
		return false;
	}
	else {
		return true;
	}
}

ull power (ull x, ull y) {
	ull result = 1;
	while (y) {
		if (y % 2) {
			result = result * x;
		}
		x = x * x;
		y /= 2;
	}
	return result;
}

ull power_modular_mod (ull x, ull y) {
	ull result = 1;
	while (y) {
		if (y % 2) {
			result = result * x % mod;
		}
		x = x * x % mod;
		y /= 2;
	}
	return result;
}

ull power_modular_phimod (ull x, ull y) {
	ull result = 1;
	while (y) {
		if (y % 2) {
			result = result * x % phimod;
		}
		x = x * x % phimod;
		y /= 2;
	}
	return result;
}

ull power_modular_phimod_log10 (ull x, char* P, int L) {
	ull result = 1;
	for (int i = L - 1; i >= 0; i--) {
		result = result * power_modular_phimod(x, P[i] - '1' + 1) % phimod;
		x = power_modular_phimod(x, 10);
	}
	return result;
}

(C11, 12ms, 1116KB, 제출번호 55100051)

---

제가 사용한 $10^{7}$은 소인수가 2개밖에 없는 수이므로, chinese remainder theorem을 적용하기도 매우 수월합니다. 다만 CRT를 적용했을 때 어느정도 더 빨라질 지는 잘 모르겠습니다.

 

제일 시간을 줄이기 좋은 방법은 $B^{C}$에서 한 번 더 Euler's Theorem을 적용하는 것 같은데, 여기까진 아직 해보지 않았습니다.