NKOJ 3805 距离（线性筛）

发表于 |
字数统计: 756字 | 阅读时长 ≈ 4min

P3805距离

问题描述

对于两个正整数a、b，这样定义函数d(a,b)：每次操作可以选择一个质数p，将a变成a*p或a/p，

如果选择变成a/p就要保证p是a的约数，d(a,b)表示将a变成b所需的最少操作次数。
例如d(69,42)=3。

现在给出n个正整数A1,A2,…,An，对于每个i (1<=i<=n)，求最小的j(1<=j<=n)使得i≠j且d(Ai,Aj)最小。

输入格式

第一行一个正整数n (2<=n<=100,000)。
第二行n个正整数A1,A2,…,An (Ai<=1,000,000)。

输出格式

输出n行，依次表示答案。

样例输入

6
1
2
3
4
5
6

样例输出

2
1
1
2
1
2

分析一下容易发现，最对于一个数对$(a,b)$最优的变化方法就是$a->gcd(a,b)->b$
那么，如果我们用$cnt[x]$表示$x$所含的质因数的个数，比如$cnt[8]=3$
显然有$d(a,b)=cnt[a]+cnt[b]-2*cnt[gcd(a,b)]$
那么对于一个数$a$我们需要找出最优的$b$
不妨考虑枚举$gcd$,那么$b$是$gcd$的倍数，但是如果枚举$gcd$再枚举$b$显然要超时。
观察发现上式中$cnt[a]$为定值，那么如果我们对于每一个$gcd$处理出使$F[gcd]=cnt[b]-cnt[gcd]$最小的$b$，就能很快解决问题，而这显然是可以预处理出来的，只需要枚举$b$的因数，用$b$更新$F$即可。
注意到不能选到相等的下标，因此我们需要记录最小和次小。
最后，$cnt$可以线性筛预处理出来，$F$可以枚举因数预处理出来，时间复杂度$O(n\times \sqrt{n})$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define max(a,b) ((a>b)?(a):(b))
#define N 1234567
using namespace std;
int n,Max,A[N],Cnt[N],cnt,P[N],F1[N],F2[N],ans,Num;
void EUL()
{
	int i,j;
	for(i=2;i<=Max;i++)
	{
		if(!Cnt[i])Cnt[i]=1,P[++cnt]=i;
		for(j=1;j<=cnt&&P[j]*i<=Max;j++)
		{
			Cnt[i*P[j]]=Cnt[i]+1;
			if(i%P[j]==0)break;
		}
	}
}
void Cha(int i,int j)
{
	if(Cnt[A[i]]<=Cnt[A[F1[j]]])F2[j]=F1[j],F1[j]=i;
	else if(Cnt[A[i]]<=Cnt[A[F2[j]]])F2[j]=i;
}
void Pre()
{
	int i,j;
	for(i=n;i>=1;i--)
	{
		for(j=1;j*j<=A[i];j++)
		if(A[i]%j==0)
		{
			Cha(i,j);
			if(j*j!=A[i])Cha(i,A[i]/j);
		}
	}
}
void MD(int x,int i)
{
	int t,k;
	if(F1[x]!=i)k=F1[x];
	else k=F2[x];
	t=Cnt[A[k]]-2*Cnt[x];
	if(t<ans||(t==ans&&k<Num))ans=t,Num=k;
}
int main()
{
	int i,j,x;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&A[i]),Max=max(A[i],Max);
	Cnt[0]=1e9;EUL();Pre();
	for(i=1;i<=n;i++)
	{
		ans=1e9;Num=1e9;
		for(j=1;j*j<=A[i];j++)if(A[i]%j==0)MD(j,i),MD(A[i]/j,i);
		printf("%d\n",Num);
	}
}