백준 10407번 2 타워(C++)

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

10407번: 2 타워

 

 수식을 찾아 모두 저장해놓는 방식으론 시간상으로나 메모리 상으로나 절 대 풀수없다. 조금 더 읽어보니 중요한 포인트는 3으로 나눈 나머지를 출력하는 것이었다.

위 함수는 오일러의 파워타워 함수에서 x에 2를 넣은 모습이다. 

먼저 H의 따른 답을 적어보면 다음과 같다. 

 

H = 3 에서 

 

4 * 4 mod 3 = (4 mod 3 ) * (4 mod 3) * mod 3 이다.  모듈러 정리인데 이를 알면 매우 쉽게 풀 수 있다. 

여기서 이산수학의 induction 방법으로 증명해보자

 

그러므로 

H = 1을 제외하면 모두 1이 나올 수 밖에 없다. 이전의 모듈러 연산을 한 수가 계속해서 다음 연산에 사용되기 때문이다. 그러므로 코드는 매우매우 간단해진다.

 

#include<iostream>
#define ll long long
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll H;

    cin >> H;

    if(H == 1)
        cout << "2" << '\n';
    else
        cout << "1" << '\n';

    return 0;
}