可以對每個Ai的所有約數xi求它到Ai的距離，然后被枚舉的所有數維護他到Ai的最小值和次小值，然后對每個Ai求Aj的時候就可以枚舉它的約數，如果最小值i和j重復就詢問次小值
code：
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;const int maxn = 110000;const int maxm = 1100000;int a[maxn],n;int p[maxm],PRi,minp[maxm],s[maxm];bool v[maxm];void pre(){ memset(v,false,sizeof v); s[1]=0; pri=0; for(int i=2;i<maxm;i++) { if(!v[i]) { p[++pri]=i; minp[i]=i; s[i]=1; } for(int j=1;j<=pri;j++) { int k=i*p[j]; if(k>=maxm) break; v[k]=true; minp[k]=p[j]; s[k]=s[i]+1; if(i%p[j]==0) break; } }}int d[maxm][2],di[maxm][2];void g_d(){ memset(d,63,sizeof d); for(int i=1;i<=n;i++) { int x=a[i]; int k=sqrt(x); for(int j=1;j<=k;j++) { int l=j; if(x%j==0) { if(d[j][0]>s[x/j]) { d[j][1]=d[j][0]; di[j][1]=di[j][0]; d[j][0]=s[x/j]; di[j][0]=i; } else if(d[j][1]>s[x/j]) { d[j][1]=s[x/j]; di[j][1]=i; } if(j*j==x) break; j=x/j; if(d[j][0]>s[x/j]) { d[j][1]=d[j][0]; di[j][1]=di[j][0]; d[j][0]=s[x/j]; di[j][0]=i; } else if(d[j][1]>s[x/j]) { d[j][1]=s[x/j]; di[j][1]=i; } } j=l; } }}int main(){ pre(); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); g_d(); for(int i=1;i<=n;i++) { int x=a[i]; int k=sqrt(x); int ansx=INT_MAX,ansy=n+1; for(int j=1;j<=k;j++) if(x%j==0) { int jl=j; int xk=x/j; int l=di[j][0]==i; int nws=s[xk]+d[j][l]; if(ansx>nws||(ansx==nws&&ansy>di[j][l])) { ansx=nws; ansy=di[j][l]; } if(j*j==x) break; j=x/j; xk=x/j; l=di[j][0]==i; nws=s[xk]+d[j][l]; if(ansx>nws||(ansx==nws&&ansy>di[j][l])) { ansx=nws; ansy=di[j][l]; } j=jl; } printf("%d/n",ansy); } return 0;}新聞熱點
疑難解答
