CF1280H

CF1280H - Make Square

题目大意

给定一个序列(a_i)

设一个数(n)的分解为(n=prod prime_i^{c_i})

每次查询一个区间([l,r])

询问在区间内选两个数(a_i,a_j (i e j))

使得(a_icdot a_j)的分解(sum (c_imod 2))最小

分析

考虑对于每个(a_i)求出集合(odd(i)={prime_i|2 ot |c_i})

这个分解质因数可以在(O(frac{sqrt a_i}{ln a_i}))的时间内完成

然后考虑选择两个数之后，实际上是求(|odd(i)Delta odd(j)|_{min})

其中(Delta)为集合对称差|异或

而容易通过按calculator发现(|odd(i)|leq 7)

那么我们可以暴力枚举(odd(i))与(odd(j))相同的部分，剩下的部分包含的元素个数就是答案

相同的部分容易用另一个数(x)表示，那么实际上就是对于每个(x)，找到删除个数最少的两个(i,j)

考虑依次加入每个点(i)，单调栈维护前面(j)的情况

容易发现(j)不同的值只有(8)个，可以用树状数组暴力处理，复杂度为

(O(ncdot 2^7cdot 7log n+qlog n))

因为常数小，可以跑进1s

const int N=2e5+10,M=5.1e6+10,INF=1e9+10;

int n,m;
int stk[M][9],T[M];
int A[N];

struct BIT{
	int s[N];
	BIT(){ memset(s,63,sizeof s); }
	void Add(int p,int x){
		while(p) cmin(s[p],x),p-=p&-p;
	}
	int Que(int p){
		int res=1e8;
		while(p<=n) cmin(res,s[p]),p+=p&-p;
		return res;
	}
} tr;

vector <Pii> G[N];

int notpri[N],pri[N],pc;
int F[N],C,U[1<<8];
void Fac(int n){
	C=0;
	for(int i=1;pri[i]*pri[i]<=n;++i) if(n%pri[i]==0) {
		int c=0;
		while(n%pri[i]==0) c^=1,n/=pri[i];
		if(c) F[C++]=pri[i];
	}
	if(n>1) F[C++]=n;
}
int ans[M];

int main(){
	rep(i,2,N-1) if(!notpri[i]){
		pri[++pc]=i;
		for(int j=i;j<N;j+=i) notpri[j]=1;
	}
	n=rd(),m=rd();
	rep(i,1,n) A[i]=rd();
	rep(i,1,m){
		int l=rd(),r=rd();
		G[r].pb(mp(i,l));
	}
	rep(i,1,n) {
		Fac(A[i]);
		rep(S,0,(1<<C)-1){
			if(S==0) U[S]=1;
			else U[S]=U[S&(S-1)]*F[__lg(S&-S)];
			int x=U[S],t=C-__builtin_popcount(S); // cost
			rep(i,1,T[x]) {
				tr.Add(stk[x][i]&((1<<20)-1),(stk[x][i]>>20)+t);
			}
			while(T[x] && (stk[x][T[x]]>>20)>=t) T[x]--;
			stk[x][++T[x]]=t<<20|i;
		}
		for(auto v:G[i]) ans[v.first]=tr.Que(v.second);
	}
	rep(i,1,m) printf("%d
",ans[i]);
}