백준 24059번: Function

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

24059번: Function

---

 

이전에 포스팅했던 12445번 문제와 비슷한 결의 문제입니다.

2021.07.19 - [분할 정복을 이용한 거듭제곱/정수 거듭제곱] - 백준 12445번: バクテリアの増殖 (Small)

 

그래서 접근법도 거의 같습니다. 문제에서 주어진대로 풀고, $n=2$ 일 때만 Euler's Theorem 을 적용하면 끝입니다.

 

그나마 팁이 있다면, 주어지는 $m$ 의 값이 소수이므로 $\phi \left ( m \right )=m-1$ 이라는 것입니다.

 

이상에서 정답 코드는 다음과 같습니다.

 

/*
 * Author : thdtjdals3
 * Date : 2022-01-11
 * Description : BOJ 24059
 * Link : https://www.acmicpc.net/problem/24059
 */

#include <stdio.h>

long long power_modular(long long a, long long p, long long m);

int main() {
	
	long long n;
	scanf("%lld", &n);
	
	long long array[3];
	for (int i = 0; i <= n; i++)
	{
		scanf("%lld", &array[i]);
	}
	
	long long m;
	scanf("%lld", &m);
	
	if (n == 0)
	{
		printf("%lld", array[0] % m);
	}
	else if (n == 1)
	{
		long long answer = array[0];
		answer = power_modular(array[1], answer, m);
		printf("%lld", answer);
	}
	else
	{
		long long temp = array[0];
		temp = power_modular(array[1], temp, m - 1);
		temp += m - 1;

		long long answer = array[2];
		answer = power_modular(answer, temp, m);

		printf("%lld", answer);
	}
	
	return 0;
}

long long power_modular (long long a, long long p, long long m)
{
	long long result = 1;
	while(p)
	{
		if (p % 2)
		{
			result = result * a % m;
		}
		a = a * a % m;
		p /= 2;
	}
	return result;
}

(C11, 0ms, 1116KB, 제출번호 37849821)

---