题解 P3532 【[POI2012]ODL-Distance】

kczno1 · 2017-02-01 21:50:42 · 题解

dis(a,b)=a*b/(gcd(a,b)^2)的质因数个数

预处理每个数的质因数个数num。

考虑枚举gcd。

也就是枚举x,对于x，枚举所有x的倍数a。

那么dis(a,b)=num(a)+num(b)-2*num(x)

那么对于每个a,选择的b就应该是最小的那一个。

我们求出num最小的，对于非最小用它更新答案，同时更新最小答案。

这样虽然不能保证x是a,b的gcd，但是a,b的gcd一定会被枚举到，所以答案一定会被更新成最优的。

#include<bits/stdc++.h>
using std::swap; 

#define U 1000000
#define N 100100
int num[U+5],t[U+5];
void init_num()
{
    static int p[N],top;
    for (int i=2;i<=U;++i)
    {
      if (!num[i])
      {
           p[++top]=i;
           num[i]=1;
      }
      int x;
      for (int j=1;(x=p[j])*i<=U;++j)
      {
            num[x*i]=num[i]+1;
          if (!(i%x)) break;     
      }
    }
}

int a[N],next[N];
int ansj[N],ans[N];
int q[N],top;

int main()
{
    freopen("1.in","r",stdin);
    init_num();
    int n,i;
    scanf("%d",&n); 
    for (i=1;i<=n;++i) 
    {scanf("%d",a+i);ans[i]=U;
     next[i]=t[a[i]];t[a[i]]=i;
    }
    int x,j;
    for (x=1;x<=U;++x)
    {
        top=0;
        for (i=1;i<=U/x;++i)
         for (j=t[x*i];j;j=next[j]) q[++top]=j;
        int b=q[1];
        for (i=2;i<=top;++i)
        if (num[a[q[i]]]<num[a[b]]||num[a[q[i]]]==num[a[b]]&&q[i]<b) swap(b,q[i]);
        for (i=2;i<=top;++i)
        {
            int A=q[i],now=num[a[A]]+num[a[b]]-(num[x]<<1);
            if (now<ans[A]||now==ans[A]&&b<ansj[A]) 
            {
                ans[A]=now;ansj[A]=b;
            }
            if (now<ans[b]||now==ans[b]&&A<ansj[b]) 
            {
                ans[b]=now;ansj[b]=A;
            }
        }
    }
    for (i=1;i<=n;++i) printf("%d\n",ansj[i]);
}