[백준] 31478 : 포니양은 놀고 싶어!

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

문제 분석

 일반적인 정수론 문제이다. $A^{B^C}$와 $\frac {B^C} {A}$의 값에 $\text {mod 7}$을 적용한 값을 구하는 것이 핵심인 문제이다. 

 $A^{B^C}$의 경우 $B^C$가 매우 큰 값을 가지므로 페르마 소정리를 통해 식을 단순화 시킬 필요가 있다. 페르마 소정리를 따르면 소수인 p에 대해 p와 서로소인 a의 p-1승의 p에 대한 나머지는 1로 표현가능하다. 이때, 7은 소수이고 A는 [1,6]의 범위로 7과 항상 서로소인 값으로 페르마 소정리를 통해 다음의 식이 성립한다. $A^{B^C} \text { mod 7} = A^{(B^C \text { mod 6} )}\text { mod 7}$ 간략화한 식을 통해 두 번에 걸친 modular 연산을 포함한 power 연산을 거치면 최종값을 구할 수 있다.

$a^{p-1}\equiv 1\pmod p$
$\rightarrow a^{6}\equiv 1\pmod 7$

 $\frac {B^C} {A}$의 경우는 $ B^C $의 경우 modular 연산을 포함한 power 연산을 수행하고 $A$의 경우 모듈러 역원을 사용하여 계산을 수행하면 최종값을 구할수있다. 

문제 해결 전략

 우선 modular 연산을 포함하여 거듭 제곱을 수행하는 power 함수를 정의한다. 이때, power연산은 분할정복을 통해 구현하여 시간복잡도를 줄인다.

 또한, 두번째 케이스를 위한 모듈러의 역원을 [1,6]의 범위에만 존재하면 되므로 하드코딩을 통해 배열을 미리 정의한다.

 후에, 앞서 설명한 방식대로 두번의 power연산으로 1번째 케이스를 다루고 power연산과 모듈러의 역원의 곱으로 2번째 케이스를 다루고 최종적으로 K와 더한 값과 L 값과의 비교로 최종출력을 정하면 된다.

코드

#include <iostream>

using namespace std;

int A, B, C;
int K, L;

int power(int base, int exponent, int mod)
{
    base=base%mod;
    if(exponent==1 || base==0){
        return base;
    }
    if(exponent==0 || base==1){
        return 1;
    }
    int temp = power(base,exponent/2,mod)%mod;


    if (exponent%2){
        return (temp*temp*base)%mod;
    }
    else{
        return (temp*temp)%mod;
    }
}

int modular_inverse[7] = {-1,1,4,5,2,3,6};
int main()
{
    cin >> A >> B >> C;
    cin >> K >> L;
    int ans1=power(A,power(B,C,6),7);
    int ans2=(power(B,C,7)*modular_inverse[A])%7;
    if((K+ans1)%7==L){
        if((K+ans2)%7==L){
            cout << 3 << "\n";
        }
        else{
            cout << 1 << "\n";
        }
    }
    else{
        if((K+ans2)%7==L){
            cout << 2 << "\n";
        }
        else{
            cout << 0 << "\n";
        }
    }
}