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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
map<int, int> dp;
int n, l[310], c[310];
int gcd(int a, int b)
{
return !b ? a : gcd(b, a % b);
}
void solve()
{
dp[0] = 0;
map<int, int>::iterator it;
for (int i = 1; i <= n; i++)
{
for (it = dp.begin(); it != dp.end(); it++)
{
int temp = gcd(l[i], it->first);
if (dp.find(temp) != dp.end())
dp[temp] = min(dp[temp], c[i] + it->second);
else
dp[temp] = c[i] + it->second;
}
}
}
signed main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> l[i];
for (int i = 1; i <= n; i++)
cin >> c[i];
solve();
if (dp.find(1) == dp.end())
{
cout << "-1" << endl;
return 0;
}
cout << dp[1] << endl;
}
|