XJOI网上同步训练DAY5 T1

思路:考虑得出，最终的集合一定是gcd=1的集合，那么我们枚举n个数中哪个数必须选，然后把它质因数分解，由于质数不会超过9个，可以状态压缩，去得出状态为0的dp值就是答案。

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 int n,l[],c[],p[],val[],f[][];

 int read(){

     int t=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 int main(){

     n=read();

     int ans=<<;

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

      l[i]=read();

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

      c[i]=read();

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

         int tot=,t=l[i];

         for (int j=;j*j<=t;j++){

             if (t%j==){

                 tot++;p[tot]=j;

                 while (t%j==) t/=j;

             }

         }

         if (t!=) p[++tot]=t;

         for (int j=;j<=n;j++)

          if (j!=i){

             val[j]=;

             for (int k=;k<=tot;k++)

              if (l[j]%p[k]==)

               val[j]|=<<(k-);

          }

         int sum;

         val[i]=sum=(<<tot)-;

         for (int j=;j<=n;j++)

          for (int k=;k<=sum;k++)

           f[j][k]=<<;

         f[i][sum]=c[i];

         for (int j=i;j<=n-;j++)

          for (int k=;k<=sum;k++)

           if (f[j][k]!=<<){

             f[j+][k]=std::min(f[j+][k],f[j][k]);

             f[j+][k&val[j+]]=std::min(f[j+][k&val[j+]],f[j][k]+c[j+]);

           }

         if (f[n][]!=<<){

             ans=std::min(ans,f[n][]);

         }

     }

     if (ans!=<<) printf("%d\n",ans);

     else

     printf("-1\n");

     return ;

 }