문제 링크: http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2021

설명

매우 큰 수를 좋아하는 사람들은 이 문제를 관심 있게 읽을 것입니다. 다음은 대규모 수 생성 방법의 예시입니다:

• 거듭제곱: 42^2016 = 42 × 42 × ... × 42 (2016번 반복)
• 팩토리얼: 2016! = 2016 × 2015 × ... × 2 × 1

이 문제에서는 'exponial'이라는 연산을 탐구합니다. 모든 양의 정수 n에 대해 정의된 이 연산은 다음과 같습니다. exponial(n) = n^(n-1)^(n-2)^⋯^2^1 예시로 exponial(5) = 5^4^3^2^1 ≈ 6.206 × 10^183230으로, 매우 큰 수입니다. 거듭제곱은 우측 연산자 우선순위를 따릅니다: a^b^c = a^(b^c).

exponial 값은 너무 커서 계산에 어려움이 있으므로, exponial(n) mod m 값을 계산하는 프로그램을 작성해야 합니다.

입력

여러 테스트 케이스가 존재합니다. 각 케이스는 두 정수 n(1 ≤ n ≤ 10^9)과 m(1 ≤ m ≤ 10^9)로 구성됩니다.

출력

exponial(n) mod m 값을 출력합니다.

샘플 입력

2 42
5 123456789
94 265

샘플 출력

2
16317634
39<br></br><br></br>해법: 이 문제는 지수 순환 정리를 활용한 오일러 함수 적용 문제입니다. A^B mod C를 계산할 때, B가 매우 클 경우 A^(B mod φ(C) + φ(C)) mod C 공식을 사용합니다. 여기서 φ(C)는 C보다 작고 C와 서로소인 정수 개수입니다.

코드 예시:

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 typedef long long ll;
 5 int n, m;
 6 
 7 ll compute_euler(int num) {
 8     ll result = num;
 9     for(int i = 2; i * i <= num; i++) {
10         if(num % i == 0) {
11             result = result / i * (i - 1);
12             while(num % i == 0) num /= i;
13         }
14     }
15     if(num > 1) result = result / num * (num - 1);
16     return result;
17 }
18 
19 ll power_mod(int base, int exponent, ll mod) {
20     ll result = 1;
21     while(exponent > 0) {
22         if(exponent & 1) result = (ll)result * base % mod;
23         base = (ll)base * base % mod;
24         exponent >>= 1;
25     }
26     return result;
27 }
28 
29 ll calculate_expo(int num, ll mod) {
30     if(mod == 1) return 0;
31     if(num == 1) return 1 % mod;
32     if(num == 2) return 2 % mod;
33     if(num == 3) return 9 % mod;
34     if(num == 4) return (1LL << 18) % mod;
35     return (ll)power_mod(num, compute_euler(mod), mod) * power_mod(num, calculate_expo(num - 1, compute_euler(mod)), mod) % mod;
36 }
37 
38 int main() {
39     while(~scanf("%d%d", &n, &m)) {
40         printf("%lld\n",calculate_expo(n, m));
41     }
42     return 0;
43 }

문의 사항은 QQ(공지사항 참조)로 연락주세요.