洛谷题解满了于是就来这里写了
大致题意
给出 $n$ 张卡片，分别有 $l_i$ 和 $c_i$。在一条无限长的纸带上，你可以选择花 $c_i$ 的钱来购买卡片 $i$，从此以后可以向左或向右跳 $l_i$ 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不行，输出 $-1$。
题解
分析该问题，发现想要跳到每一个格子上，必须使得所选数 $l_{i_1}, \dots, l_{i_k}$ 通过数次相加或相减得出的绝对值为 $1$，也即存在整数 $x_1, \dots, x_n$ 使得 $l_{i_1} x_1 + \cdots + l_{i_k} x_k = 1$。由多个整数的裴蜀定理逆定理，这相当于 从数组 $l_1, \dots, l_n$ 选择若干个数，满足它们的最大公因数为 $1$，同时要求代价和最小。
注：（给不熟悉裴蜀定理的人）
裴蜀定理：设 $a,b$ 是不全为零的整数，则存在整数 $x,y$, 使得 $ax+by=\gcd(a,b)$.
多个整数裴蜀定理：设 $a_1, a_2, \dots, a_n$ 是不全为零的整数，则存在整数 $x_1, x_2, \dots, x_n$, 使得 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n=\gcd(a_1, a_2, \dots, a_n)$。其逆定理也成立：设 $a_1, a_2, \dots, a_n$ 是不全为零的整数，$d > 0$ 是 $a_1, a_2, \dots, a_n$ 的公因数，若存在整数 $x_1, x_2, \dots, x_n$, 使得 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n=d$，则 $d = \gcd(a_1, a_2, \dots, a_n)$。
好了，现在问题已经转化成了一个动态规划问题。如果看了刚才的定理有点忘了的话，那就再把这个问题重申一遍：
从数组 $l_1, \dots, l_n$ 选择若干个数，满足它们的最大公因数为 $1$，同时要求代价和 $\sum\limits_{l_i}^{} c_i$ 最小。（$l_i$ 是被选中的）
仔细一看——这是不是有点像 0-1 背包？
让我们来回顾一下普通的 0-1 背包求的是什么：在 $(\sum\limits_{}^{} w_i)<W$ 时，$max(\sum\limits_{}^{} v_i)$。（$i$ 是被选中的）
而对于这个问题，只不过是把价值改成了代价，又改了改限制条件而已
我们设 $f_{i, j}$ 表示考虑前 $i$ 个数且 最大公因数为 $j$ 的 最小代价（注意与普通 0-1 背包对比，后者是设 $f_{i, j}$ 表示考虑前 $i$ 个数且 和为 $j$ 的 最大价值），则有转移方程：
$f_{i, j} = \min_{\gcd(k, l_i) = j} f_{i - 1, k} + c_i.$
（请自行对比普通 0-1 背包转移方程以获得更深的理解）
DP 后最终的总代价即为 $f_{n, 1}$。
然而这样的复杂度是 $O(n\sum\limits_{}^{} a_i)$，会 TLE。
考虑一个简单的优化：即消去无用状态。
我们只需要开个 map，每次把访问过的 $x$ 执行转移即可，这样就能轻松过题了。
事实上，这题用 unordered_map 应该更优，比较这题只需建立映射关系就行，不需要 map 那样的自动有序特性。
如果不想用 map 之类的 STL ，那么也可以如同一般的 0-1 背包问题，可以用滚动数组优化，去掉第一维。总之优化方法非常多，也都比较简单。
因此，这就是裴蜀定理+01背包+gcd=紫题
代码（可能有点抽象）
#include<bits/stdc++.h>
using namespace std;
const int N=305;
int n,l[N],c[N];
map<int,int> pre;
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]);
pre[l[1]]=c[1];
for(int i=2;i<=n;i++)
{
for(auto k:pre) pre[__gcd(k.first,l[i])]==0?pre[__gcd(k.first,l[i])]=k.second+c[i]:pre[__gcd(k.first,l[i])]=min(pre[__gcd(k.first,l[i])],k.second+c[i]);
pre[l[i]]=min((pre[l[i]]==0)?INT_MAX:pre[l[i]],c[i]);
}
printf("%d",pre[1]==0?-1:pre[1]);
}
十八行切掉的水紫