[POI2012]Odległość

[POI2012]Odległość

题目大意：

一个长度为(n(nle10^5))的序列(A(1le A_ile10^6))，定义(d(i,j))为每次对(A_i,A_j)中的一个数乘一个质数(p)，让(A_i=A_j)的最少操作步数。

对于每个(i)，求能使(d(i,j))最小的(j)，若有多个解，输出最小的(j)。

思路：

用(f(x))表示(x)所有质因子次数之和，则(d(i,j)=f(A_i)+f(A_j)-2f(gcd(A_i,A_j)))。

对于每个(A_i)，枚举其约数作为(gcd)，对于每个约数记录其倍数(x)中最小、次小的(f(x))。

时间复杂度(mathcal O(nsqrt m))。

这样能在BZOJ通过，但是不能在SZKOpuł上通过。官方题解提供的做法是(mathcal O(nloglog n))。

源代码：

#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
const int N=1e5+1,A=1e6+1;
int a[N],d[A],p[A];
bool vis[A];
std::pair<int,int> min[A][2];
inline void sieve(const int &n) {
	for(register int i=2;i<=n;i++) {
		if(!vis[i]) {
			d[i]=1;
			p[++p[0]]=i;
		}
		for(register int j=1;p[j]*i<=n;j++) {
			vis[p[j]*i]=true;
			d[p[j]*i]=d[i]+1;
			if(i%p[j]==0) break;
		}
	}
}
inline void upd(const int &j,const int &i) {
	std::pair<int,int> tmp=std::make_pair(d[a[i]]-d[j]*2,i);
	if(tmp<min[j][0]) std::swap(tmp,min[j][0]);
	if(tmp<min[j][1]) std::swap(tmp,min[j][1]);
}
int main() {
	const int n=getint();
	for(register int i=1;i<=n;i++) {
		a[i]=getint();
	}
	const int m=*std::max_element(&a[1],&a[n]+1);
	sieve(m);
	for(register int i=1;i<=m;i++) {
		min[i][0]=min[i][1]=std::make_pair(INT_MAX,INT_MAX);
	}
	for(register int i=1;i<=n;i++) {
		for(register int j=1;j*j<=a[i];j++) {
			if(a[i]%j) continue;
			upd(j,i);
			if(j*j!=a[i]) upd(a[i]/j,i);
		}
	}
	for(register int i=1;i<=n;i++) {
		std::pair<int,int> ans=std::make_pair(INT_MAX,INT_MAX);
		for(register int j=1;j*j<=a[i];j++) {
			if(a[i]%j) continue;
			ans=std::min(ans,min[j][min[j][0].second==i]);
			ans=std::min(ans,min[a[i]/j][min[a[i]/j][0].second==i]);
		}
		printf("%d
",ans.second);
	}
	return 0;
}