[洛谷4139]上帝与集合的正确用法题解

朱雀 2021-11-26 12:42 106阅读 0赞

**前言**  
非常interesting的[题目][Link 1]，立个flag下一道做洛谷P3934 Nephren Ruq Insania  
UPD(2019.5.21)：[flag完成了][flag]  
**解法**  
题目求\\(2^\{2^\{2^\{2\\dots\}\}\}\\ \\%\\ p\\)的值  
珂以递归解决，根据[欧拉降幂][Link 2]将\\(2^\{2^\{2^\{2\\dots\}\}\}\\ \\%\\ p\\)转化为\\(2^\{2^\{2^\{2^\{2\\dots\}\}\}\\ \\%\\ phi\[p\] + phi\[p\]\} % p\\)  
于是我们就愉快的递归解决，显然当递归到\\(p\\)为\\(1\\)时，结果为\\(0\\)，结束。

**代码**

#include <cstdio>
    #define ll long long
    
    inline ll read(){
        ll x = 0; int zf = 1; char ch = ' ';
        while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
        if (ch == '-') zf = -1, ch = getchar();
        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
    }
    
    int phi[10000005];
    
    ll getPhi(int MAXNUM){
        for(int i = 1; i <= MAXNUM; ++i)
            phi[i] = i;
        for(int i = 2; i <= MAXNUM; i += 2)
            phi[i] >>= 1;
        for(int i = 3; i <= MAXNUM; i += 2)
            if(phi[i] == i)
                for(int j = i; j <= MAXNUM; j += i)
                    phi[j] = phi[j] / i * (i - 1);
    }
    
    ll pow(ll a, ll b, ll mod){
        if (!a) return 0;
        ll ans = 1;
        for ( ; b; b >>= 1, a = (a * a) % mod)
            if (b & 1)
                ans *= a, ans %= mod;
        return ans;
    }
    
    ll solve(ll mod){
        if (mod == 1) return 0;
        return pow(2, solve(phi[mod]) + phi[mod], mod);
    }
    
    int main(){
        getPhi(10000000);
        int T = read();
        for (int I = 0; I < T; ++I)
            printf("%lld\n", solve(read()));
        return 0;
    }

转载于:https://www.cnblogs.com/linzhengmin/p/10896301.html

[Link 1]: https://www.luogu.org/problemnew/show/P4139
[flag]: https://www.luogu.org/recordnew/show/19240010
[Link 2]: https://www.cnblogs.com/linzhengmin/p/10896065.html