[13970] Power towers

문제 링크 : https://www.acmicpc.net/problem/13970

13970 - Power towers

본문

Suppose that we have a non empty list of positive integers: $[x_1, x_2, \cdots, x_N]$. The power tower corresponding to this list is the number defined as:

\[x_1^{x_2^{.^{.^{.^{x_n}}}}}, \text{ that is } x_1^{\left(x_2^{\left(.^{.^{.^{x_n}}}\right)}\right)}\]

Power towers can be very big numbers, even when the list consists of only a few small integers. For example, the power tower of the list $[2, 3, 2]$ is equal to $2^9 = 512$, and that of $[5, 2, 3, 2]$ is equal to $5^{512}$ and has 358 decimal digits. In this task, you will have to compute power towers modulo a given positive integer M.

입력

The first line of the input will contain two positive integers: $T$ and $M$. Each of the following $T$ lines will contain a positive integer $N$, followed by a list of $N$ positive integers $x_1, x_2, \cdots, x_N$. There will be exactly one space separating consecutive numbers in all lines of the input.

출력

The output must contain $T$ lines, each containing a single non-negative integer. The number in line $k$ must be equal to the result of the power tower for the $k$-th given list modulo $M$.

제한

시간 제한	메모리 제한
2sec	512MB

$1 \leq T \leq 1000$
$1 \leq \text{sum of the lengths } N \leq 1000000$ (1e6)
$1 \leq x_i \leq 1000000$ (1e6)

풀이

문제를 처음 보고 이해만 며칠, 구상만 며칠, 계획 며칠, 구현 며칠.. 어질어질하다. 이제부터는 간단해보이면서도 다이아 문제면 3주일은 잡고 풀어야겠다..

일단 문제의 이해부터 단계로 진행하자. 숫자들의 list가 주어지고, 우리는 그것을 탑 형식으로 거듭제곱시켜 그 결과를 얻고 싶다. 이 숫자는 너무 커지므로 원래의 답에 모듈러를 취해 그 값을 출력할 계획이다.

일단 그럼 답을 어떻게 계산해야하는지 생각해보자. 예시로 주어지는 리스트를 아래와 같이 생각해보자.

\[\text{input : } [a, b, c, d], \text{mod : m}\]

이렇게 되면 우리는 $a^{b^{c^d}} \mod m$ 의 결과를 얻고 싶은 것이 된다. $b^{c^d} = e$라고 치환하면 $a^e \mod m$의 꼴로 적을 수 있겠다. 이 형태의 식이라면, 문제를 좀 풀어봤다 싶은 사람들은 어떤 정리가 떠오를 것이다.

바로 페르마의 소정리이다. 간단히 얘기하면, 어떤 소수 $p$에 대하여 $a^{p-1} \equiv 1 \mod p$를 만족한다는 정리이다. 그래서, $e$의 값이 매우 커지더라도, 우리는 $a^e \equiv a^{(e \% (p-1))} \pmod p$이라고 계산할 수 있다는 것이다. 문제에서 주어지는 모듈러의 값이 1백만 이하이므로, 우리가 고려해야할 $d$의 값은 커져봤자 1백만이 될 것이다. 문제의 단위를 매우 축소시킬 수 있다.

하지만 페르마의 소정리를 활용하기 위해서는 2가지 조건이 필요하다.

모듈러 연산을 진행하는 숫자 $p$는 소수이어야 한다
거듭제곱되는 수 $a$에 대해, $\gcd(a, p) = 1$이어야 한다

아쉽게도, 문제에서 주어지는 조건들은 이 조건들을 둘 다 만족시키지 않는다. 즉 페르마의 소정리를 그냥 쓸 수는 없다는 것이다.

그나마 다행히도, “$p$가 소수이어야 한다”는 조건을 일반화시킨 다른 정리가 존재한다고 한다. 그것이 오일러 정리. 페르마 소정리를 일반화한 것이라고 이해하면 될 것 같다. 오일러 정리는 두 정수 $a, n$에 대하여 $\gcd(a, n) = 1$이라면 $a^{\phi(n)} \equiv 1 \mod n$이라고 한다. 즉 입력되는 모듈러가 굳이 소수가 아니어도, $a$와 서로소이기만 한다면 위 공식을 적용할 수 있다는 의미이다.

처음으로 돌아와서, 입력이 $[a, b, c, d]$이고 모듈러가 $m$인 문제라고 생각하면, 우리는 아래와 같이 오일러 정리를 이용하여 계산할 수 있게 된다. 이 때 표현을 쉽게 하기 위해, $[a, b, c, d] \rightarrow a^{b^{c^d}}$라고 이해하자.

문제의 정의에 의해, $[a, b, c, d] \equiv a^{[b,c,d]} \pmod{m}$
이 때, $\gcd(a, m) = 1$이라면 오일러 정리에 의해 $[a, b, c, d] \equiv a^{[b,c,d] \text{ (mod } \phi{(m)})} \pmod{m}$

이 경우, a의 지수 부분을 잘 보자. 지수를 또 다른 문제라고 생각해보면, 배열의 길이가 1 줄었고 모듈러의 값도 $\phi{(m)}$으로 바뀌었다. 일단 배열의 길이를 1 줄였다는 것은 문제를 축소시켰다고 볼 수 있다. 그리고 또 생각해보면, $\phi(m) < m$이라는 것이 항상 보장된다. 따라서, 우리는 오일러 정리를 통해 기존 문제를 더 작은 문제로 축소시켜 풀어낼 수 있다는 것을 의미한다. 이를 풀어낼 함수를 구상해보자.

특정 단계를 풀어내는 함수를 재귀적으로 돌리면 될 것 같다. 리턴값을 $[b, c, d] \text{ mod } z = x$라고 줄 수 있다면, $a^{func([b,c,d], \phi{(m)})} \text{ mod } m$을 계산하도록 하면 재귀적으로 돌아갈 수 있을 것이다. 함수의 입력에 주어지는 배열과 모듈러 값은 재귀가 진행될 때마다 계속해서 줄어드는 경향이 있다. 그러니 exit point만 잘 잡아주면 된다.

모듈러 값이 $1$인 경우, $0$을 반환해야할 것이다. 모든 정수는 $1$로 나눈 나머지가 $0$이니까
배열의 특정 부분에서 $1$이 등장하였다면, 뒤는 계산하지 말고 $1$을 반환할 수 있다. $1^{x} = 1$이니까
배열에 숫자가 1개밖에 존재하지 않는 경우, 재귀를 진행하지 않고 $a \text{ mod } m$이 우리가 구하는 답이므로 바로 계산하여 보내줄 수 있다
나머지 경우는 재귀적으로 축소된 문제를 풀어 결과를 계산하도록 한다

이것을 solve함수로 구상하여 구현해보자. 이 함수는 $\phi()$값이 필요하니까 얘도 함수로 만들어두도록 하자. 그리고 거듭제곱을 할 power 함수도 필요할 것이다. 거듭제곱은 최대 1백만번 진행할 수도 있으므로, 분할정복을 이용하여 $O(\log n)$으로 구현하자.

이렇게만 끝나면 정-말 좋을텐데.. 우린 아직 하나의 조건을 해결하지 못했다. 바로 “두 수가 서로소이어야한다“는 점이다. 서로소가 아니라면 위의 이야기가 아무것도 적용되지 않는다. 말 그대로 오일러 정리를 그냥 쓰면 답이 없다는 말이다. 이 부분부터는 해결 방법을 찾을 수 없어 더 이상 진행할 수 없었다.

결론적으로 중국인의 나머지 정리를 이용하면 모듈러를 모두 소수로 바꾸어도 결과값을 얻을 수 있다는 것을 찾아냈다. 모듈러는 정수이므로 일단 소인수분해를 할 수 있고, 이 값은 유일하다. 그리고, 모든 소인수들에 대하여 $\text{mod}$ 값을 계산할 수 있다면, 나머지정리를 이용하여 그 값을 모두 묶어버릴 수 있다고 한다. 이 포스트에서는 묶는 방법에 대해서는 서술하지 않으려고 한다. 나중에 나머지정리를 주로 쓰는 문제를 풀 기회가 있다면 추가할 예정.

모듈러 $m$이 정수 $a$와 서로소가 아닌 것이 문제이므로, 나머지정리를 활용하기 위해 $m$을 소인수분해하여 결과를 찾아보자.

$m$은 소수들 $p_i$에 대해 $p_1^{e_1} \times p_2^{e_2} \times \cdots p_k^{e_k}$로 나타낼 수 있고, 이 값은 $m$에 대해 유일하다
- 만약 $\gcd{(a, p_k^{e_k})} = 1$이라면, solve값은 기존 방법대로 계산할 수 있다
- 만약 아니라면, $a$는 $p_k$를 소인수로 가지고 있다는 뜻이 된다
  - 여기서 중요한데, 만약 $[b, c, d]$의 값이 $e_k$보다 크거나 같다면, $[a, b, c, d]$는 $p_k^{e_k}$의 배수라는 것이 증명된다.
  - 즉, 추가로 해결해야하는 부분은 $[b, c, d]$의 값이 $e_k$보다 작은 부분을 찾아야한다는 것이다. 문제의 조건에 의해, $e_k$의 값은 커봤자 $20$일 것이다 (모듈러로 나오는 수가 최대 1백만이니까)
    - 이 부분은 $[b, c, d]$의 값을 직접 계산해보도록 하자. 계산하는 도중 그 어떤 부분에서도 $20$을 넘어가는 수가 나온다면 결과값은 항상 20보다 클 것이므로, $[a,b,c,d]$는 $p_k^{e_k}$의 배수라고 생각할 수 있다
    - 만약 $[b,c,d]$의 값이 $e_k$보다 작다면, 나머지를 구해야한다. 다행히도 $[b,c,d]$의 값은 20보다 작으므로, 그냥 $a^{[b,c,d]} \text{ mod } p_k^{e_k}$를 구할 수 있다
위 과정을 통해 모든 수들을 구하고, 그것을 나머지정리로 묶어내면 답을 얻을 수 있다

…. 이런 생각은 어떻게 하고 문제를 풀어내는거지..

참고 알고리즘 : 오일러 정리, 중국인의 나머지 정리

코드

사용 언어 : C
최종 수정일 : 2023 / 2 / 17

  
#include <stdio.h>

typedef long long ll;

#define MAX_IDX (int)(1e6)
int arr[MAX_IDX];
int m;

int phi(int x) {
    int retval = 1;
    for (int i = 2; i * i <= x; ++i) {
        int k = 0;
        int p = 1;
        while (x % i == 0) {
            ++k, p *= i;
            x /= i;
        }

        if (k > 0) {
            p /= i;
            retval *= (p * (i - 1));
        }
    }

    if (x > 1) {
        retval *= (x - 1);
    }
    return retval;
}
int gcd(int a, int b) {
    int temp = 0;
    while (b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}
int inverse(int a, int m) {
    int m0 = m;
    int y = 0;
    int x = 1;

    if (m == 1) {
        return 0;
    }
    while (a > 1) {
        int q = a / m;
        int t = m;

        m = a % m;
        a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0) {
        x = x + m0;
    }

    return x;
}
int chineseRemainder(int mod, int pe, ll r) { return ((mod / pe) * (inverse(mod / pe, pe) * r)); }
ll powWithModulo(ll x, int y, int mod) {
    ll ret = 0;
    if (y == 0) {
        return 1;
    } else if (y == 1) {
        ret = x;
    } else {
        ll xx = powWithModulo(x, y / 2, mod);
        if (y % 2 == 0) {
            ret = xx * xx;
        } else {
            ret = (xx * xx % mod) * x;
        }
    }
    return ret % mod;
}

#define INF 20
int powUntilMax(int x, int y) {
    ll ret = 0;
    if (y == 0) {
        return 1;
    } else if (y == 1) {
        ret = x;
    } else {
        int xx = powUntilMax(x, y / 2);
        if (xx >= INF) {
            return INF;
        }
        if (y % 2 == 0) {
            ret = xx * xx;
        } else {
            ret = (xx * xx) * x;
        }
    }
    return ret;
}
int getPower(int s, int e, int cur) {
    if (s == e) {
        return 0;
    } else if (s + 1 == e) {
        return powUntilMax(arr[s], cur);
    }
    if (cur >= INF) {
        return INF;
    } else if (arr[s] >= INF) {
        return INF;
    } else if (arr[e - 1] >= INF) {
        return INF;
    }

    return getPower(s, e - 1, powUntilMax(arr[e - 1], cur));
}

ll solve(int s, int e, int mod) {
    if (mod == 1) {
        return 0;
    } else if (s + 1 == e) {
        return arr[s] % mod;
    }

    if (gcd(arr[s], mod) == 1) {
        return powWithModulo((ll)arr[s], solve(s + 1, e, phi(mod)), mod);
    }

    // ai and mod is not coprime
    // loop for mod's prime set -> chinese remainder theorem
    int subMod = mod;
    ll ret = 0;

    for (int i = 2; i * i <= subMod; ++i) {
        int cnt = 0;
        int pe = 1;
        while (subMod % i == 0) {
            ++cnt, pe *= i;
            subMod /= i;
        }

        if (cnt > 0) {
            if (gcd(arr[s], i) == 1) {
                ret += chineseRemainder(mod, pe, powWithModulo((ll)arr[s], solve(s + 1, e, phi(pe)), pe));
            } else {
                int powerValue = getPower(s + 1, e, 1);
                if (powerValue < cnt) {
                    ret += chineseRemainder(mod, pe, powWithModulo((ll)arr[s], powerValue, pe));
                }
            }
        }
    }

    if (subMod > 1) {
        int cnt = 1, pe = subMod;
        if (gcd(arr[s], subMod) == 1) {
            ret += chineseRemainder(mod, pe, powWithModulo((ll)arr[s], solve(s + 1, e, phi(pe)), pe));
        }
    }

    return ret % mod;
}

int main() {
    int t;
    scanf("%d %d", &t, &m);

    while (t--) {
        int n;
        scanf("%d", &n);
        int firstOneAppear = n;
        for (int i = 0; i < n; ++i) {
            scanf("%d", arr + i);
            if (arr[i] == 1 && firstOneAppear == n) {
                firstOneAppear = i + 1;
            }
        }

        printf("%lld\n", solve(0, firstOneAppear, m));
    }
    return 0;
}

phi() : 입력으로 주어진 수의 phi 값을 반환
gcd() : 두 정수의 최대공약수를 반환. 두 수가 서로소인지 판별하기 위함
inverse() : 정수의 역원을 반환. 나머지정리 -> 모듈러 역원에서 활용
chineseRemainder() : 중국인의 나머지정리에서 하나의 방정식에서의 계산값을 반환. 모든 소인수에 대한 결과값을 합쳐야 원래의 정답을 얻을 수 있다
powWithModulo() : 모듈러 연산이 적용되는 거듭제곱 함수값을 반환. solve 함수의 리턴값으로 사용
powUntilMax() : 모듈러 연산이 적용되지 않는 거듭제곱 함수값을 반환. getPower()에서 사용
getPower() : 특정 범위의 배열값을 계산하여 반환. $\gcd{(a, p_k^{e_k})} > 1$일 때, $[a,b,c,d]$가 $p_k^{e_k}$의 배수인지 판별하기 위함
solve() : 문제의 정답을 반환. 문제를 더 작은 문제의 재귀 형식으로 풀어나감

[13970] Power towers

13970 - Power towers

본문

입력

출력

제한

풀이

코드

Further Reading

[1916] 최소비용 구하기

[15686] 치킨 배달

[1253] 좋다