[16214] N과 M

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

16214 - N과 M

본문

임의의 자연수 $N$과 $M$이 주어져 있다. $A^B$를 $A$의 $B$승이라고 할 때, 수열 $N$, $N^N$, $N^{(N^N)}$, $N^{(N^{(N^N)})}$, … 의 수들을 $M$으로 나눈 나머지는 수열의 어느 지점부터 항상 일정한 값을 가진다. $N$과 $M$이 주어져 있을 때, 이 일정한 나머지 값을 계산하라.

입력

첫 번째 줄에는 질의의 개수 $T$가 주어진다. 질의는 1개 이상 1000개 이하이다.

두 번째 줄부터 $T+1$번째 줄까지는 각 질의에 해당하는 자연수 $N$과 $M$이 주어진다. $N$과 $M$은 둘 다 $10^9$ 이하이다.

출력

각 질의의 $N$과 $M$에 대해, $N^{(N^{(N^{(N^\cdots)})})}$의 값을 $M$으로 나눈 나머지를 구하여라. 나머지의 값은 $0$ 이상 $M$ 미만이어야 한다.

제한

시간 제한	메모리 제한
1sec	1024MB

• $0 < N, M \leq 10^9$

---

풀이

문제를 보면 power tower의 case 중 하나임을 알 수 있다. power tower는 입력되는 input의 수가 달랐는데, 이 문제에서는 그 입력되는 수들이 $N$으로 고정되서 주어진다. 그래서, power tower 문제를 풀 수 있는 코드를 가져오면 그대로 답을 얻을 수 있다.

수는 $N$이랑 $M$만 입력되므로, 우리가 직접 power tower의 입력으로 사용될 배열을 만들어주어야한다. 그 때 배열의 길이가 애매한데, 입력으로 주어지는 모듈러 $M$이 10억까지 가능하므로, 지수값 중 가장 큰 $2^{31}$에 의거하여, 배열의 길이를 여유롭게 33까지만 지정해주었다.

power tower를 구하는 자세한 방법은 “참고 알고리즘”을 참고하자.

• 참고 알고리즘 : Power Tower

코드

사용 언어 : C

최종 수정일 : 2023 / 1 / 9

#include <stdio.h>

typedef long long ll;

#define MAX_IDX 33
ll arr[MAX_IDX];
ll m;

ll phi(ll x) {
    ll retval = 1;
    for (ll i = 2; i * i <= x; ++i) {
        ll k = 0;
        ll 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;
}
ll gcd(ll a, ll b) {
    ll temp = 0;
    while (b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}
ll inverse(ll a, ll m) {
    ll m0 = m;
    ll y = 0;
    ll x = 1;

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

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

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

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

    return x;
}
ll chineseRemainder(ll mod, ll pe, ll r) { return ((mod / pe) * (inverse(mod / pe, pe) * r)); }
ll powWithModulo(ll x, ll y, ll 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 31
ll powUntilMax(ll x, ll y) {
    ll ret = 0;
    if (y == 0) {
        return 1;
    } else if (y == 1) {
        ret = x;
    } else {
        ll xx = powUntilMax(x, y / 2);
        if (xx >= INF) {
            return INF;
        }
        if (y % 2 == 0) {
            ret = xx * xx;
        } else {
            ret = (xx * xx) * x;
        }
    }
    return ret;
}
ll getPower(ll s, ll e, ll 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(ll s, ll e, ll mod) {
    if (mod == 1) {
        return 0;
    } else if (arr[s] == 1) {
        return 1;
    } else if (s + 1 == e) {
        return arr[s] % mod;
    }

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

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

    for (ll i = 2; i * i <= subMod; ++i) {
        ll cnt = 0;
        ll 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(arr[s], solve(s + 1, e, phi(pe)), pe));
            } else {
                ll powerValue = getPower(s + 1, e, 1);
                if (powerValue < cnt) {
                    ret += chineseRemainder(mod, pe, powWithModulo(arr[s], powerValue, pe));
                }
            }
        }
    }

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

    return ret % mod;
}

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

    while (t--) {
        ll n;
        scanf("%lld %lld", &n, &m);
        for (int i = 0; i < MAX_IDX; ++i) {
            arr[i] = n;
        }

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