Description：

给一个序列 $a[]$ ，定义 $d(i,j)$ 为每次对 $a[i],a[j]$ 之一乘一个质数 $p$ 或除以一个质数 $p$ ，让 $a[i]=a[j]$ 的最少操作步数。

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

$1\leqslant n\leqslant 10^5,1\leqslant a[i]\leqslant 10^6$

Solution：

首先发现 $d(i,j)=\frac{a[i]}{\gcd(a[i],a[j])}\times \frac{a[j]}{\gcd(a[i],a[j])}$ ，求出来 $div[i]$ 表示 $i$ 分解成的质数个数，那么有 $d(i,j)=div[a[i]]+div[a[j]]-2\times div[\gcd(a[i],a[j])]$ ，那么我们可以枚举 $k$ 作为 $\gcd(a[i],a[j])$ ，再枚举一个 $k$ 的倍数作为 $a[i]$ ，这样我们只要最小化 $div[a[j]]$ 即可，那么我们可以再预一个 $div[a[j]]$ 的最小值和次小值来更新，因为不能选重复的，但是这样可能 $k\ne \gcd(a[i],a[j])$ ，但是没关系，因为这样的话一定不如 $k'=\gcd(a[i],a[j])$ 时的值优，所以必然不会成为最后的答案，注意在预处理最大值和次大值的时候细节很多。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int a[MAXN];

#define MAX 1000001

bool isprime[MAX];

int prime[MAX],tot = 0;

int mindiv[MAX];

int d[MAX];

void sieve()

{

	for(int i = 2;i < MAX;++i)isprime[i] = true;

	for(int i = 2;i < MAX;++i)

	{

		if(isprime[i])

		{

			mindiv[i] = i;

			prime[++tot] = i;

		}

		for(int j = 1;j <= tot && i * prime[j] < MAX;++j)

		{

			isprime[i * prime[j]] = false;

			mindiv[i * prime[j]] = prime[j];

			if(i % prime[j] == 0)break;

		}

	}

	for(int i = 2;i < MAX;++i)

	{

		d[i] = d[i / mindiv[i]] + 1;

	}

	return;

}

int gcd(int a,int b){return (b == 0 ? a : gcd(b,a % b));}

vector<int> v[MAX];

int ans[MAX],res[MAX];

bool smaller(int x,int y)

{

	if(d[a[x]] < d[a[y]])return true;

	if(d[a[x]] > d[a[y]])return false;

	if(x < y)return true;

	else return false;

}

int main()

{

	sieve();

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)

	{

		v[a[i]].push_back(i);

	}

	memset(ans,0x3f,sizeof(ans));

	for(int i = 1;i < MAX;++i)

	{

		int fi = 0,se = 0;

		for(int j = i;j < MAX;j += i)

		{

			for(vector<int>::iterator it = v[j].begin();it != v[j].end();++it)

			{

				if(fi == 0)fi = *it;

				else

				{

					if(smaller(*it,fi))se = fi,fi = *it;

					else if(se == 0 || smaller(*it,se))se = *it;

				}

			}

		}

		if(se == 0)continue;

		for(int j = i;j < MAX;j += i)

		{

			for(vector<int>::iterator it = v[j].begin();it != v[j].end();++it)

			{

				if(*it == fi)

				{

					if(d[a[*it]] + d[a[se]] - 2 * d[i] < ans[*it])

					{

						ans[*it] = d[a[*it]] + d[a[se]] - 2 * d[i];

						res[*it] = 0x3f3f3f3f;

					}

					if(d[a[*it]] + d[a[se]] - 2 * d[i] == ans[*it])

						res[*it] = min(res[*it],se);

				}

				else

				{

					if(d[a[*it]] + d[a[fi]] - 2 * d[i] < ans[*it])

					{

						ans[*it] = d[a[*it]] + d[a[fi]] - 2 * d[i];

						res[*it] = 0x3f3f3f3f;

					}

					if(d[a[*it]] + d[a[fi]] - 2 * d[i] == ans[*it])

						res[*it] =  min(res[*it],fi);

				}

			}

		}

	}

	for(int i = 1;i <= n;++i)printf("%d\n",res[i]);

	return 0;

}