P1405

Stairs_upon_temple · 2024-01-04 16:32:26 · 题解

本题唯一一个不用递归过的题解！

记住公式 a^b=a^{b\ \bmod\ \varphi(m)+\ \varphi(m)}\pmod m。

任何情况下均可使用(不分是否互质)。

简单推一下：

依此类推：

每次只需求出当前次数下的模数并类推下一次。

将每一次求出的模数结果存下来。

再用欧拉公式进行降幂。

即可在标准时间内通过。

注意细节，每次快速幂求解时应加上每次取余的值，不然到后面 \varphi 值为 1 时， 最后一个要乘方的数会计算成 1。

/*
g++ -o2 P1405.cpp -o c -std=c++14
.\c

*/

#include<bits/stdc++.h>
#include<cstdio>
using namespace std;

typedef long long ll;
typedef __int128 in;
const in N=2e6+100;
const in MOD=10007;
in max(in a,in b){return a>b?a:b;}
in min(in a,in b){return a<b?a:b;}

ll n;
ll phi[N];
ll mod[N];

in ask(in m){  //求欧拉函数
    in sum=m;
    for(in i=2;i*i<=m;i++){
        if(m%i==0){
            sum=sum/i*(i-1);
            while(m%i==0) m/=i;
        }
    }
    if(m>1) sum=sum/m*(m-1);
    return sum;
}

in mul(in a, in b, in p){ //快乘，但没什么卵用
    a%=p,b%=p;
    long double z=(long double)a/p*b;
    in z2=z;
    in r=a*b-z2*p;
    if(r<0)r+=p;
    return r;
}

in mul_add(in a,in b,in p)
{
    in ans=0;
    while(b){
        if(b&1) ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return ans;
}

void init(){  //初始化模数
    phi[1]=MOD;
    for(in i=2;i<=n+100;i++){
        phi[i]=ask(phi[i-1]);
    }
    return ;
}

in quick_pow(in a,in b,in mod){   //快速幂
    in sum=1;
    while(b){
        if(b&1){
            sum=mul_add(sum,a,mod);
            if(sum>=mod)sum=sum%mod+mod;
        }
        a=mul_add(a,a,mod);
        if(a>=mod)a=a%mod+mod;
        b>>=1;
    }
    return sum;
}

int main(){
    scanf("%lld",&n);
    init();
    // for(int i=1;i<=100;i++)printf("%lld ",phi[i]);
    // printf("\n");
    for(in i=1;i<=n;i++){
        scanf("%lld",&mod[i]);
        // if(phi[i]==1)mod[i]=1;
        // else if(mod[i]>=phi[i])mod[i]=(mod[i]%phi[i]+phi[i]);
    }
    in sum=1;
    in flag=0;
    for(in i=n;i>=1;i--){
        in dis=sum;
        sum=quick_pow(mod[i],sum,phi[i]);
        if(sum==1 && mod[i]!=1)sum+=phi[i];
        if(phi[i]==1)sum=1;
        if(sum==0)sum+=phi[i];
        // ll a=sum;
        // ll b=mod[i];
        // ll c=sum;
        // ll d=phi[i];
        // printf("%lld : %lld %lld %lld\n",a,b,c,d);
    }
    ll s=sum%MOD;
    printf("%lld\n",s);
    return 0;
}

/*
5
2 2 2 50 641

*/