定理

存在整数 xx，yy 使得 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)

证明：

考虑求 gcd⁡(a,b)\gcd(a,b) 的过程，

gcd⁡(a,b)→gcd⁡(b,r1)→gcd⁡(r1,r2)→⋯→gcd⁡(rn−1,rn)=1\gcd(a,b)\to\gcd(b,r_1)\to\gcd(r_1,r_2)\to\cdots\to\gcd(r_{n-1},r_n)=1

拆开取模成带余除法

a=bx1+r1b1=r1x2+r2r1=r2x3+r3⋯rn−3=rn−2xn−1+rn−1(1)rn−2=rn−1xn+rn(2)rn−1=rnxn+1\begin{aligned} a&=bx_1+r_1\\ b_1&=r_1x_2+r_2\\ r_1&=r_2x_3+r_3\\ &\cdots\\ r_{n-3}&=r_{n-2}x_{n-1}+r_{n-1}&\quad(1)\\ r_{n-2}&=r_{n-1}x_{n}+r_n&(2)\\ r_{n-1}&=r_{n}x_{n+1}\\ \end{aligned}

辗转相除到 rn=1r_n=1 时退出，由 (2)(2) 式 rn−2=xnrn−1+rnr_{n-2}=x_nr_{n-1}+r_n 得：

1=rn−2−xnrn−1(3)1=r_{n-2}-x_nr_{n-1}\quad(3)

将 (1)(1) 式 rn−1=rn−3−rn−2xn−1r_{n-1}=r_{n-3}-r_{n-2}x_{n-1} 代入 (3)(3) 式，得 1=(1+xnxn−1)rn−2−xnrn−31=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3} 成功消去 rn−1r_{n-1} ，再一步步递归，就能消去 rn−2,rn−3,⋯ ,r1r_{n-2},r_{n-3},\cdots,r_1 然后就能得到关于 aa 和 bb 的式子了。

一道题目

CF510D Fox And Jumping

给出 nn 张卡片，分别有 lil_i 和 cic_i。在一条无限长的纸带上，你可以选择花 cic_i 的钱来购买卡片 ii，从此以后可以向左或向右跳 lil_i 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不行，输出 −1-1。

就是求在 nn 个数中选出若干个 gcd⁡=1\gcd=1 的数的最小代价。

抽象一点，设当前到达的位置为 xx ，代价为 dd ，可以枚举 1...n1...n ，用 d+cid+c_i 更新 gcd⁡(x,li)\gcd(x,l_i) 的值，相当于从 xx 节点到 gcd⁡(x,li)\gcd(x,l_i) 连一条长为 cic_i 的边，跑一遍从 00 到 11 的最短路，求出 d1d_1 即可。

节点编号是原始数据 ll 的值域，发现区间较大，可以用 unordered_map 代替标记数组。

注意细节：

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
typedef long long ll;
typedef pair<ll, int> pii;

unordered_map <int, bool> vis;
unordered_map <int, ll> dis;
priority_queue <pii, vector<pii>, greater<pii>> q;

void calc() {
    dis[0] = 0;
    q.push(make_pair(0, 0));
    memset(&inf, 0x3f, sizeof(decltype(inf)));
    while (q.size()) {
        int u = q.top().second;
        q.pop();
        if (vis.find(u) != vis.end()) continue;
        vis[u] = true;
        if (u == 1) break;
        for (int i = 1, v; i <= n; i++) {
            v = gcd(u, l[i]);
            if (dis.find(v) == dis.end()) {//记住不是 vis.find(v) != vis.end()，因为有可能 dis 有值而还没有遍历到
                dis[v] = inf;
            }
            if (dis[v] > dis[u] + c[i]) {  
                dis[v] = dis[u] + c[i];
                q.push(make_pair(dis[v], v));
            }
        }
    }
    if (vis.find(1) == vis.end()) {
        cout << -1 << endl;
    } else {
        cout << dis[1] << endl;
    }
}