CF510D

发表于 更新于 分类于
Fox And Jumping

Fox And Jumping

首先是裴蜀定理，据此很容易判断，此题要求我们取若干个数的 $\gcd$ 为 1，然后使代价最小。

考虑 DP。

可是 map 那玩意的复杂度完全没办法证明。。。

状压这种方式还是稳妥一些。

令 $S$ 的每一位表示 $l _ i$ 的第 $j$ 小质因数是否存在，这样就能很好的表示我们需要的数了，因为一个数的质因数最多只有 9 个。

转移当然就是随便搞搞，取公共质因数的交集之类的。。。

然后我们每次用 $f(i,0)$ 与答案比较，取最小值即可。

时间复杂度 $O( n ^ 3 \log ^ 3 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=3e2,M=1e3;

ll n;
ll a[N+5],c[N+5],f[N+5][M+5],cnt[N+5],fac[N+5][15];

inline ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}

inline void Solve(ll i,ll j,ll Si,ll Sj) {
  ll tmpS=0;
  for(ll x=0;x<cnt[i];x++) {
    ll flg=0;
    for(ll y=0;y<cnt[j];y++) {
      if(!((Sj>>y)&1)) continue;
      if(fac[i][x]==fac[j][y]) {flg=1;break;}
    }
    if(flg) tmpS|=(1<<x);
  }
  f[i][tmpS]=min(f[i][tmpS],f[j][Sj]+c[i]);
}

inline ll Init(ll x,ll id) {
  ll amt=0;
  for(ll i=2;i*i<=x;i++) {
    if(x%i==0) {
      fac[id][amt++]=i;
      while(x%i==0) x/=i;
    }
  }
  if(x>1) fac[id][amt++]=x;
  return amt;
}

int main() {

  n=read();

  ll tmp=0;
  for(ll i=1;i<=n;i++) {
    a[i]=read();if(a[i]<0) a[i]=-a[i];
    if(a[i]!=0) tmp=gcd(a[i],tmp);
  }
  for(ll i=1;i<=n;i++) {c[i]=read();}
  
  if(tmp!=1) writeln(-1);
  else {
    memset(f,0x3f,sizeof(f));
    ll ans=f[0][0];
    for(ll i=1;i<=n;i++) {
      cnt[i]=Init(a[i],i);
      ll tmp=(1<<cnt[i])-1;
      f[i][tmp]=c[i];
      for(ll j=1;j<i;j++) {
        for(ll p=0;p<(1<<cnt[j]);p++) {
          Solve(i,j,tmp,p);
        }
      }
      ans=min(ans,f[i][0]);
    }
    write(ans);
  }

  return 0;
}