[POI 19 Stage 1] Distance

作法：

設d[ i ] 代表 i 是由幾個質數乘起來得到的，例如d[ 8 ] = 3 ，那麼就可以知道 x 和 y 的距離就等於 d[ x ] + d[ y ] - 2 * d[ gcd( x , y ) ] 。所以當我們在算一個數 x 的答案時，我們可以枚舉所以他的因數，用來當 gcd( x , y ) ，而在確定了這兩個數之後，剩下的目的就變成要讓 d[ y ] 越小越好。所以對每個數，我們可以紀錄在數列裡的哪個數是他的 d 值最小而且又是那個數的倍數的。並且之後直接查詢就好了。但這樣會有個問題，如果 x 的某個因數 z ，他紀錄下來的數恰好是 x ，那就沒有用了，所以應該要保存兩個最佳解，兩個都試試看。

最後還要注意到的是，當我們去看 z 的最佳的兩個倍數的時候，他和 x 的 gcd 值不一定是 z ，可能會是 z 的倍數，但這個方法可以保證找到最佳的解。這個的證明也不難，因為如果有個沒被找到的話就可以推出那個數不會是最佳解。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 , maxm=1000000+10 ;
 
int vis[maxm] ;
int la[maxm],MA=0 ;
void prime()
{
     for(int i=2;i*i<=MA;i++) if(!vis[i])
          for(int j=i*i;j<=MA;j+=i) vis[j]=1 , la[j]=i ;
}
 
int d[maxm] ;
void getd()
{
     d[1]=0 ;
     for(int i=2;i<=MA;i++) d[i]= vis[i] ? d[i/la[i]]+1 : 1 ;
}
 
int getdis(int x,int y)
{
     int g=__gcd(x,y) ;
     return d[x]+d[y]-2*d[g] ;
}
 
struct P
{
     int id,val ;
     bool operator < (const P &rhs) const
     {
          return d[val]==d[rhs.val] ? id<rhs.id : d[val]<d[rhs.val] ;
     }
};
 
P v[maxm][3] ;
int sz[maxm] ;
void PB(int vid,const P &p)
{
     v[vid][sz[vid]++]=p ;
     if(sz[vid]==3)
     {
          for(int i=0;i<2;i++) for(int j=2;j>i;j--)
               if(v[vid][j]<v[vid][j-1]) swap(v[vid][j],v[vid][j-1]) ;
          sz[vid]-- ;
     }
}
 
int a[maxn] ;
main()
{
     int n ; scanf("%d",&n) ;
     for(int i=1;i<=n;i++) scanf("%d",&a[i]) , MA=max(MA,a[i]) ;
 
     prime() ;
     getd() ;
     for(int i=1;i<=n;i++)
          for(int j=1;j*j<=a[i];j++) if(a[i]%j==0)
     {
          PB(j,(P){i,a[i]}) ;
          if(a[i]!=j*j) PB(a[i]/j,(P){i,a[i]}) ;
     }
 
     for(int i=1;i<=n;i++)
     {
          int ans=maxm , id=n+1 ;
 
          for(int j=1;j*j<=a[i];j++) if(a[i]%j==0)
               for(int t=0;t<2;t++)
          {
               int x= (t==0 ? j : a[i]/j) ;
               if(v[x][0].id==i && sz[x]==1) continue ;
 
               P tmp= (v[x][0].id==i ? v[x][1] : v[x][0]) ;
               int val=getdis(tmp.val,a[i]) ;
               if(val<ans || (val==ans && tmp.id<id))
                    ans=val , id=tmp.id ;
          }
          printf("%d\n",id) ;
     }
}