백준 4862번: 마지막 자리

 

www.acmicpc.net/problem/4862

4862번: 마지막 자리

---

기본 이론1 글에서 잠깐 언급했던 Euler's Theorem을 활용하는 문제입니다.

 

코드를 제시하기에 앞서, Euler's Theorem은 다음과 같습니다.

 

$\LARGE a^{b} \equiv a^{b mod \varphi \left ( N \right )} \left ( mod N \right )$

 

이때 $\varphi \left ( N \right )$ 을 Euler Totient Function이라고 부르는데, 다음과 같이 구할 수 있습니다.

 

( 복잡도 $O \left ( \sqrt{N} \right )$ )

 

long long phi (long long K) { // O(sqrt(n))
	long long result = K;
	long long i;
	for (i = 2; i * i <= K; i++) {
		if (K % i == 0) {
			result -= result / i;
			while (K % i == 0) {
				K /= i;
			}
		}
	}
	if (K > 1) {
		result -= result / K;
	}
	return result;
}

 

n의 범위가 1~7이므로 $10^{n}$의 범위가 상당히 작습니다.

 

따라서 $O \left ( \sqrt{N} \right )$ 으로 구해도 충분하다는 걸 알 수 있습니다.

 

이렇게 구현한 phi 함수를 이용하여 문제를 풀려 했으나, 한 가지 주의할 점이 있었습니다.

 

$f\left ( x \right )= b^{f\left ( x-1 \right )}=b^{b^{f\left ( x-2 \right )}}=\cdots$

 

이 과정에서 $b^{b}$ , $b^{b^{b}}$, ... 등의 mod $10^{n}$ 값을 구하게 되는데, 중간에 0이 나오게 되면 결과가 꼬이는 것이었습니다.

 

그래서 mod 값이 0이 나오지 않도록 새로 mod 함수를 구현하여 사용했습니다.

 

long long newmod (long long a, long long b) { // A mod B
    if (a > b) {
        return b + a % b;
    }
    else {
        return a;
    }
}

 

이 newmod 함수를 이용하여 power_modular 함수를 구현했고,

 

최종적으로 $f\left ( 1 \right ), f\left ( 2 \right ), \cdots, f\left ( x-1 \right ), f\left ( x \right )$를 재귀적으로 구하는 방식으로 전체 코드를 구현했습니다.

 

#include <stdio.h>

long long phi (long long K); // euler's totient function

long long newmod (long long a, long long b); // A mod B
long long power_modular (long long a, long long b, long long M); // a ^ b (mod M)

long long function_modulo (long long x, long long b, long long M); // f(x) = b^(f(x-1))

int main() {
    
	long long b, i, n, temp;
	long long Mod;
	char string[8];
    
	scanf("%lld", &b);
    
	while (b != 0) {
		scanf("%lld", &i);
        
		scanf("%lld", &n);
		temp = n;
		string[n] = '\0';
        
		Mod = 1;
		while(n > 0) { // Mod = 10^n
			Mod *= 10;
			n--;
		}
        
		long long result = function_modulo(i, b, 10000000) % Mod;
        
		while(temp > 0) {
			temp--;
			string[temp] = '0' + (result % 10);
			result /= 10;
		}
        
		printf("%s\n", string);
		
		scanf("%lld", &b);
	}
	return 0;
}

long long phi (long long K) { // O(sqrt(n))
	long long result = K;
	long long i;
	for (i = 2; i * i <= K; i++) {
		if (K % i == 0) {
			result -= result / i;
			while (K % i == 0) {
				K /= i;
			}
		}
	}
	if (K > 1) {
		result -= result / K;
	}
	return result;
}

long long newmod (long long a, long long b) { // A mod B
    if (a > b) {
        return b + a % b;
    }
    else {
        return a;
    }
}

long long power_modular (long long a, long long b, long long M) { // a ^ b (mod M)
	long long result = 1;
	while (b) {
		if (b & 1) {
			result = newmod (result * a, M); // result < 10^8
		}
		a = newmod (a * a, M); // a < 10^8
		b >>= 1;
	}
	return result;
}

long long function_modulo (long long x, long long b, long long M) {
	if (x == 0) {
		return 1;
	}
	else {
		long long PHI = phi(M);
		long long F = function_modulo (x-1, b, PHI); // a^b = a ^ (b mod phi(m)) (mod m)
		return power_modular (b, F, M);
	}
}

(C11, 1116KB, 548ms, 제출번호 25533470)

---

github.com/pkkj/ACM-ICPC-OJ-Code/blob/master/ICPC.Regional/2005.Rocky_Mountain/la3343.cpp

위 링크에서 많은 아이디어를 빌렸습니다.

 

저는 처음에 Euler's Theorem을 적용할 생각도 못했지만,

 

사실 power tower 유형이라 불리는 이 유형에서는 일반적인 풀이 같기도 합니다.

 

또 phi 함수의 구현 같은 경우는 위 링크의 표현이 이해가 힘들어 이 사이트에서 아이디어를 빌렸습니다.

(이제보면, 위 링크에서 phi 함수 구현에 사용된 j는 $1 + 3 + 5 + \cdots + \left ( 2n-1 \right )=n^{2}$ 에서 착안한 것 같습니다만...)

cp-algorithms.com/algebra/phi-function.html#toc-tgt-1