题解 P4139 【上帝与集合的正确用法】

NaCly_Fish · 2018-12-12 22:14:18 · 题解

发现这题其实是我出过一题的弱化版。。
传送门：link

题目要求出：

的值

根据扩展欧拉定理：
此处 \varphi 指的就是数论中的欧拉函数，证明略。网上一搜一大堆。

我们不难想到这样的一个递归函数，用来求 a^{a^{a^{...}}}\text{mod }p（n 个 a）。
由于是这个乘方塔有无限层，b 肯定大于 \varphi(p)，所以直接用第一种情况即可。

int tower(int a,int n,int p){
    if(p==1) return 0;
    if(n==1) return c%p;
    int t = phi(p);
    return power(a,tower(a,n-1,t)+t,p);
}

（这里 phi 是求欧拉函数的）

可是题目中让求的是无限层，并不是有限层，怎么办啊？
不要紧，在一层层的递归中，p 一遍遍的被求其 \varphi 值，最终必定会降到 1。原因很简单：

• 对任意大于 1 的整数 p，\varphi (p) 是偶数。
• 若 p 是偶数，\varphi(p) \leq p/2。

第二条可以利用欧拉函数的积性，从中提取 2 这个质因子来证明。由此可以发现，这个递归过程只会进行 \mathcal O(\log p) 次。

然后我们就有办法了，求答案的时候直接用一个很大的 n 来计算就好啦！
注意做快速幂时每次模数不同，需要注意一下。

参考代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

inline int phi(int n){  
    int res,a;
    res = a = n;
    for(int i=2;i*i<=a;++i){
        if(a%i) continue;
        res = res/i*(i-1);  
        while(!(a%i)) a /= i;
    }  
    if(a>1) res = res/a*(a-1);
    return res;  
}

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)){
        x = (x<<3)+(x<<1)+c-'0';
        c = getchar();
    }
}

inline int power(int a,int t,int p){
    int res = 1;
    while(t){
        if(t&1) res = (ll)res*a%p;
        a = (ll)a*a%p;
        t >>= 1;
    }
    return res;
}

int tower(int c,int p){ // 这里稍微改了一下，直接求解，不用设置一个很大的 n
    if(p==1) return 0;
    int t = phi(p);
    return power(c,tower(c,t)+t,p);
}

void print(int x){
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

void optimized(){
    int m;
    read(m);
    print(tower(2,m));
    putchar('\n');
}

int main(){
    int T;
    read(T);
    while(T--)
        optimized(); 
    return 0;
}