前置知识
解法
本题幂塔是有限层的,这里与 luogu P4139 上帝与集合的正确用法 中的无限层幂塔不同,故需要在到达递归边界时进行特殊处理,对于处理 \(varphi(p)\) 在递归过程中等于 \(1\) 的情况两题基本一致。
回忆扩展欧拉定理中的 \(b\) 和 \(\varphi(p)\) 的关系,如果我们按照 常规的快速幂写法 会出现问题,即我们无法正确判断 \(a^b\) 在作为下一次运算的指数时和 \(\varphi(p)\) 之间的大小关系,这就需要我们额外在快速幂的过程中判断 \(a^b\) 和 \(\varphi(p)\) 之间的大小关系。
- 在这里可以使用
__int128_t
来代替实现高精度的快速幂。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll __int128_t
#define sort stable_sort
#define endl '\n'
ll a[1300000];
ll read()
{
ll x=0,f=1;
char c=getchar();
while(c>'9'||c<'0')
{
if(c=='-')
{
f=-1;
}
c=getchar();
}
while('0'<=c&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
ll phi(ll n)
{
ll ans=n,i;
for(i=2;i<=sqrtl(n);i++)//因为使用了__int128_t,为防止CE便使用了sqrtl,亦可以写成i*i<=n的形式
{
if(n%i==0)
{
ans=ans/i*(i-1);
while(n%i==0)
{
n/=i;
}
}
}
if(n>1)
{
ans=ans/n*(n-1);
}
return ans;
}
ll qpow(ll a,ll b,ll p)
{
ll ans=1;
while(b)
{
if(b&1)
{
ans=ans*a;
if(ans>=p)//快速幂特殊处理1
{
ans=ans%p+p;
}
}
b>>=1;
a=a*a;
if(a>=p)//快速幂特殊处理2
{
a=a%p+p;
}
}
return ans;
}
ll f(ll i,ll n,ll p)
{
return (i==n+1||p==1)?1:qpow(a[i],f(i+1,n,phi(p)),p);//对幂塔进行递归
}
int main()
{
ll n,i,p=10007;
n=read();
for(i=1;i<=n;i++)
{
a[i]=read();
}
printf("%lld\n",f(1,n,p)%p);//因为最后结果小于10007,所以可以放心大胆地当作long long输出
return 0;
}
标签:小明,return,递归,题解,ll,varphi,P1405,ans,define
From: https://www.cnblogs.com/The-Shadow-Dragon/p/17904868.html