CF906D Power Tower

扩展欧拉定理

洛谷交的第二个黑题

题意

给出一个序列\(w-1,w_2,\cdots,w_n\)，以及\(q\)个询问

每个询问给出\(l,r\)，求：

\[w_l^{w_{l+1}^{w_{l+2}^{\cdots^{w_r}}}}\bmod p
\]

\(w_i\le 10^9,p\le 10^9,n\le 10^5,q\le 10^5\)

相似题：P4139 上帝与集合的正确用法

都是用欧拉函数，如果你不知道扩展欧拉定理是啥，看这里

和那题一样，递归的处理指数，和\(p\)取模，然后每递归一层，就让\(p\leftarrow \varphi(p)\)

然后这样一层层递归下去，直到\(p=1\)或者\(l=r\)

对于任意一个偶数\(p\)，总有\(\varphi(p)\le \dfrac{p}{2}\)，因为在小于等于它的数中，一定会有\(\dfrac{p}{2}\)个数是二的倍数，不和他互质

然后又因为对于\(p>2\)，总有\(\varphi(p)\)为偶数，原因是当\(\gcd(d,p)=1,\gcd(p-d,p)=1\)（这个可以由反证法很容易的得出）

所以，对于任意一个\(p\)，先经过一次给他变成\(\varphi(p)\)，然后只要\(\log\)次就可以把它变成\(1\)，所以递归最多\(O(\log p)\)层

但是要开一个map来记录已经算出的\(\varphi\)，否则\(O(q\log p\sqrt p)\)跑不出来

还有一个问题，就是扩展欧拉定理的应用条件是\(b\ge \varphi(p)\)，\(b\)是指数

所以要判断一下\(b\)和\(\varphi(p)\)的大小关系，然而那个上帝与集合的题不用这样，因为那个是无限个\(2\)在指数上，显然\(b>\varphi(p)\)

但是，我们在下一层递归中返回的，已经是对\(\varphi(p)\)取模以后\(b\)的值了，不是真实值，无法比较

如果同时记录真实值和取模后的值又比较麻烦，所以考虑每次取模，都是如果大于等于模数，就让他取模后再加上模数，如果小于模数当然就不管

结束递归回溯的时候也要取模

\(\texttt{code.}\)

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#include<map>

#define reg register

#define EN std::puts("")

#define LL long long

inline LL read(){

	register LL x=0;register int y=1;

	register char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

int w[100006];

std::map<LL,LL>map;

inline LL get_phi(LL n){

	if(map.find(n)!=map.end()) return map[n];

	LL ret=n;

	for(reg LL i=2;i*i<=n;i++){

		if(!(n%i)) ret=ret/i*(i-1);

		while(!(n%i)) n/=i;

	}

	if(n>1) ret=ret/n*(n-1);

	map[n]=ret;

	return ret;

}

inline LL mo(LL x,LL mod){

	return x<mod?x:(x%mod+mod);

}

inline LL power(LL a,LL b,LL mod){

	LL ret=1;

	while(b){

		if(b&1) ret=mo(ret*a,mod);

		a=mo(a*a,mod);b>>=1;

	}

	return ret;

}

LL work(int l,int r,LL p){

	if(l==r||p==1) return mo(w[l],p);

	return power(w[l],work(l+1,r,get_phi(p)),p);

}

int main(){

	LL n=read(),p=read();

	for(reg int i=1;i<=n;i++) w[i]=read();

	int q=read();while(q--){

		int l=read(),r=read();

		std::printf("%lld\n",work(l,r,p)%p);

	}

	return 0;

}

巴特西

CF906D Power Tower

扩展欧拉定理

题意

最新文章

热门文章