P4139 上帝與集合的正確用法

題目鏈接

? 根據(jù)題意 求 \(2^{2^{2^ {. ^{. ^{. ^{2}}}}}} \bmod p\), 題目已說(shuō)明必然存在 \(a_n \bmod p\) 之后都是同一個(gè)值。

? 根據(jù)歐拉降冪公式：

所以我們可以考慮對(duì)指數(shù)取模。

? 其實(shí)根據(jù)\(\phi(p) \space p \ge2\) 都為偶數(shù)，由歐拉函數(shù)公式知偶數(shù)\(p\), 一定滿足不等式 \(\phi(p) \le \frac{p}{2}\), 不斷的遞歸\(\phi(p) \rightarrow \phi(\phi(p)) \rightarrow \dots\) 其實(shí)是一個(gè)不斷減小的過(guò)程，所以必然存在結(jié)束條件 \(\phi(x) = 1\), 即指數(shù)取模后為 \(0\)（若不為 \(1\) 則我們需要不斷的進(jìn)行遞歸）。

Code

#include <bits/stdc++.h>

using i64 = long long;

int phi(int x) {
    int res = x;

    for (int i = 2; i <= x / i; i ++) {
        if (x % i == 0) {
            res = res / i * (i - 1); 
            while (x % i == 0) x /= i; 
        }
    }  
    if (x > 1) res = res / x * (x - 1);

    return res;
}

i64 fast_pow(i64 a, i64 b, i64 mod) {
    i64 res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

i64 solve(i64 x) {
    if (x == 1) return 0;
    int pp = phi(x);
    return fast_pow(2ll, solve(pp) + pp, x);
}

int main() {
   int _; std::cin >> _;
   
   while (_ --) {
        int p; std::cin >> p;

        std::cout << solve(p) << "\n";
   } 
}

P4139 上帝與集合的正確用法