P12524 题解

出题人对离散对数有什么执念吗，连续两个题都要用。

平方最后算，先拆贡献，容易发现

\gcd(a_1,\dots,a_n)=\prod_{p^k|a_1,\dots,a_n}p

因此统计所有素数幂在多少个子序列出现了即可。

考虑莫队，如何插入一个数，枚举他的所有素数幂的因子，假设它已经在区间内出现了

k

次，则贡献是答案乘上

p^{2^{\max(k-1,0)}}

，其中

2^{\max(k-1,0)}

是

k

个数中长度偶数的子序列个数。可以做到

O(n^{1.5}\log^2n)

。

尝试去掉一个 log，上面的 2 的幂可以预处理，下面的可以用离散对数转成乘法计算，做到

O(n^{1.5}\log n)

。

代码粘了一堆板子。

const int P=MOD,g=3;
namespace Math{
	unordered_map<int,int>pm(5000000);
	int ff[32000];
	vi pr;
	int b,c,n,tc;
	il int qp(int x,int y){
		int z=1;
		for(;y;(x*=x)%=P,y>>=1)if(y&1)(z*=x)%=P;
		re z;
	}
	il int _Log(int x){
		x=qp(x,P-2);
		for(int i=b;;i+=b){
			(x*=c)%=P;
			if(pm.count(x))re i-pm[x];
		}
	}
	void init(){
		b=500000;c=1;
		rept(i,1,b+1){
			(c*=g)%=P;
			pm[c]=i;
		}
		n=min((int)sqrt(P)+2,P);
		rept(i,2,n){
			if(!ff[i]){
				ff[i]=_Log(i);
				pr.pb(i);
			}
			for(int j:pr){
				if(i*j>=n)break;
				ff[i*j]=(ff[i]+ff[j])%(P-1);
				if(i%j==0)break;
			}
		}
		tc=_Log(P-1);
	}
	il int Log(int x){
		if(x<n)re ff[x];
		int y=P/x,z=P%x;
		if(z*2<=x)re (tc+Log(z)-ff[y]+P-1)%(P-1);
		re (Log(x-z)-ff[y+1]+P-1)%(P-1);
	}
}
const int N=100005,B=330;
int n,q;
int a[N],c[N],pw[N],ans[N],cx[N],icx[N];
vector<array<int,4>>qy;
vi tp[N],pr;
int isp[N];
il int qp(int x,int y){
	int z=1;
	for(;y;(x*=x)%=MOD,y>>=1)if(y&1)(z*=x)%=MOD;
	re z;
}
int tmp;
il void ins(int x){
	for(int i:tp[x]){
		(tmp+=cx[i]*pw[c[i]])%=(MOD-1);
		c[i]++;
	}
}
il void era(int x){
	for(int i:tp[x]){
		c[i]--;
		(tmp-=cx[i]*pw[c[i]])%=(MOD-1);
	}
}
void run(){
	Math::init();
	rept(i,2,N){
		if(!isp[i]){
			pr.pb(i);
			int ri=Math::Log(i);
			for(int j=i;j<N;j*=i){
				cx[j]=ri;
				for(int k=j;k<N;k+=j)tp[k].pb(j);
			}
		}
		for(int j:pr){
			if(i*j>=N)break;
			isp[i*j]=1;
			if(i%j==0)break;
		}
	}
	pw[0]=pw[1]=1;
	rept(i,2,N)pw[i]=pw[i-1]*2%(MOD-1);
	cin>>n>>q;
	rep(i,n)cin>>a[i];
	rep(i,q){
		int l,r;
		cin>>l>>r;
		l--;
		qy.pb({l/B,r,l,i});
	}
	sort(all(qy));
	tmp=1;
	int l=0,r=0;
	for(auto it:qy){
		while(l>it[2])ins(a[--l]);
		while(r<it[1])ins(a[r++]);
		while(l<it[2])era(a[l++]);
		while(r>it[1])era(a[--r]);
		ans[it[3]]=tmp;
	}
	rep(i,q)cout<<qp(g,MOD*2-4+ans[i]*2)<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;
//	cin>>T;
	while(T--)
		run();
	re 0;
}

文章操作

相关推荐

评论

P12524 题解