P1405 苦恼的小明题解

hexz01 · 2024-02-24 11:17:56 · 题解

题目传送门

前置知识

1.欧拉函数

2.扩展欧拉定理

部分分做法

60 分做法

直接快速幂，做 {a_1}^{a_2} 即可。

AC 做法

首先发现指数太大，用快速幂根本没法做，于是考虑扩展欧拉定理：

发现上面两种情况可以合并为第一种情况，为了分类讨论简便，我们只需要判断 b 是否小于 \varphi(p) 即可。

设函数 sol(int l, int r, int p) 表示 {a_l}^{{a_{l+1}}^{\cdots^{a_r}}} 的值，要求这个值，就要求出 {a_{l+1}}^{\cdots^{a_r}}，也就是 sol(l+1, r, p) 的值。

加入扩展欧拉定理：

当 sol(l+1, r, p) 小于 \varphi(p) 时，sol(l+1, r, p)=sol(l+1, r, phi[p])。
当 sol(l+1, r, p) 大于 \varphi(p) 时，sol(l+1, r, p)=sol(l+1, r, phi[p])+phi[p]。

此时需要在递归求值过程中记录一个标记 flag 作为第二个返回值，表示指数是否大于 \varphi(p)。此处 flag 只需要在每个取模的地方判断是否大于模数即可，具体见代码注释。

AC code

#include <iostream>
#include <vector>
using namespace std;
const int N=20007;
int n;
int a[1234570];

//接下来线性筛欧拉函数部分，phi数组即为所求。
int pri[N], tot=0;
bool is_pri[N], phi[N];
void pre(){
    phi[1]=1;
    for(int i=2;i<=20000;i++){
        if(!is_pri[i]){
            pri[++tot]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=tot && i*j<=20000;j++){
            is_pri[i*j]=1;
            if(i%j==0){
                phi[i*j]=phi[i]*j;
                break;
            }
            phi[i*j]=phi[i]*phi[j];
        }
    }
}

//快速幂部分，传回两个值，第一个是结果，第二个是flag
pair<int, bool> ksm(int x, int y, int p){
    int ans=1;
    bool flag=0;
    if(x>=p)
        x%=p, flag=1;//第一次判断
    while(y){
        if(y&1){
            ans=ans*x;
            if(ans>=p)
                ans%=p, flag=1;//第二次判断
        }
        x=x*x;
        if(x>=p)
            x%=p, flag=1//第三次判断;
        y>>=1;
    }
    return make_pair(ans, flag);
}
pair<int, bool> sol(int l, int r, int mod){
    if(mod==1)//最多log(10007)次后mod=1，此时无论如何返回0，因为任何数mod 1 都为0
        return make_pair(0, 0);
    if(l==r){
        int tmp=a[l];
        bool flag=0;
        if(tmp>=mod)
            tmp%=mod, flag=1;//返回最后一个数时也要判断
        return make_pair(tmp, flag);
    }
    pair<int, bool> tmp=sol(l+1, r, phi[mod]);//接下来算指数
    int nowa=a[l];//当前底数
    if(tmp.second)//如果b>=phi[p]
        tmp.first+=phi[mod];//再加上phi[p]
    return ksm(al, tmp.first, mod);//返回答案（快速幂返回值意义和solve返回值意义相同，所以直接返回）
}
int main(){
    cin>>n;
    pre();
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cout<<sol(1, n, 10007).first<<endl;
    return 0;
}

P1405 苦恼的小明 题解