由裴蜀定理知道，$ax+by=gcd(a,b)$，存在一组$x,y$使该式成立，显然当$gcd(a,b)=x$时，可以跳到$x$的倍数的位置，当$gcd(a,b)=x$时，可以跳到纸带上的任意一个位置。将该式推广到$n$个数显然也成立。抽象一下，我们假设现在已经可以走到$x$了，我们枚举下一个位置，实际上就像是在做最短路，我们可以直接跑一边最短路就可以了，我用了$\text{dijsktra}$，由于值域很大，用$\text{unordered_map}$代替$\text{dis}$和$\text{vis}$数组就可以了，目前是最优解。
#include <cstdio>
#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pii;
const int maxn=305;
const ll inf=1e18;
unordered_map<int,int> vis;
unordered_map<int,ll> dis;
priority_queue<pii,vector<pii>,greater<pii> > que;
int c[maxn],n,l[maxn];
inline int gcd(int x,int y)
{
while((x%=y)&&(y%=x));
return x|y;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",l+i);
for(int i=1;i<=n;++i) scanf("%d",c+i);
dis[0]=0;
que.push(make_pair(0,0));
while(!que.empty())
{
int u=que.top().second;que.pop();
if(u==1) break;
if(vis.find(u)!=vis.end()) continue;
vis[u]=1;
for(int i=1;i<=n;++i)
{
int v=gcd(u,l[i]);
if(dis.find(v)==dis.end()) dis[v]=inf;
if(dis[v]>dis[u]+c[i])
{
dis[v]=dis[u]+c[i];
que.push(make_pair(dis[v],v));
}
}
}
if(dis.find(1)==dis.end()) puts("-1");
else printf("%lld\n",dis[1]);
return 0;
}