• 周五. 12月 9th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

#扩展欧拉定理#CF906D Power Tower

admin

11月 28, 2021

题目

给定一个数列,有(m)组询问
定义

[large f(x-1)={a_x}^{f(x)}
]

(f(r)=a_r)(f(l))
对固定的 (mod) 取模


分析

根据扩展欧拉定理

[large
egin{cases}
a^xequiv a^{xmod varphi(p)+varphi(p)}pmod p,xgeq varphi(p)\
a^x,otherwise
end{cases}
]

一次(varphi(p))至少会将下一层的模数缩小一半((p>2)
那么最多(log p)次就会结束递归,那么时间复杂度为(O(mlog mod))
注意一旦(xgeq varphi(p))一定要补上(a^{varphi(p)})才能保证正确性


代码

#include <cstdio>
#include <cctype>
#include <map>
#define rr register
using namespace std;
int n,mod,l,r,a[100011];
map<int,int>phi;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
inline void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
inline signed min(int a,int b){return a<b?a:b;}
inline void Get_Phi(int &p){
	rr int now=p,m=p;
	for (rr int i=2;i*i<=p;++i)
	if (p%i==0){
		now=now/i*(i-1);
		while (p%i==0) p/=i;
	}
	if (p>1) now=now/p*(p-1);
	p=phi[m]=now;
}
inline signed ksm(int x,int y,int p){
	rr long long ans=1,t;
	for (;y;y>>=1){
		if (y&1){
			t=ans*x;
			if (t>=p) t=t%p+p;
			ans=t;
		}
		t=1ll*x*x;
		if (t>=p) t=t%p+p;
		x=t;
	}
	return ans;
}
inline signed answ(int x,int p){
	if (x==r+1||p==1) return 1;
	rr int mi=answ(x+1,phi[p]);
	return ksm(a[x],mi,p); 
}
signed main(){
	n=iut(),mod=iut();
	for (rr int t=mod;t>1;Get_Phi(t));
	for (rr int i=1;i<=n;++i) a[i]=iut();
	for (rr int Q=iut();Q;--Q)
		l=iut(),r=iut(),print(answ(l,mod)%mod),putchar(10);
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注