HDU 2026 春季联赛 7 1001 - Card（裴蜀定理）

杭电 2026 春季联赛 7 第 1 题（HDU 1001）。原题：https://acm.hdu.edu.cn/contest/problem?cid=1203&pid=1001

题目大意

无向连通图 $n$ 点 $m$ 边，每条边有正权 $w$ 表示走这条边耗费的时间。每个点 $i$ 上有一瓶魔力药水 $a_i$ ，喝一瓶可以让魔力值 $\pm a_i$ （任意次、不耗时间）。从 $1$ 号点出发、初始魔力 $0$ ，目标让魔力值恰好等于 $V$ ，求最少总移动时间；不可达输出 -1 。

约束 $1 \le n, m \le 10^4$ ， $1 \le V, a_i, w \le 10^9$ 。题面保证 $a_1$ 的所有质因数都在 $V$ 的质因数集合中（注意这不蕴含 $a_1 \mid V$ ）。

样例

1
3 2 18
2 3 4
1 2 10
2 3 20

输出 0 。 $V = 18 = 9 \cdot a_1$ ，起点直接喝 9 次正向药水就行，不用动。

思路讲解

一句话

走过的点的 $a_i$ 通过裴蜀定理可以拼出 $\gcd$ 的所有倍数；问题等价于找一条从 $1$ 出发的路径，让经过点的 $\gcd$ 整除 $V$ ，最小化总边权。 $\gcd$ 状态只有 $O(\log V)$ 种，分层图 Dijkstra 直接跑。

裴蜀定理转化

走过点集 $S$ 时，每个点 $i \in S$ 都可以喝若干次正向 / 反向药水。最终魔力值是

$\sum_{i \in S} k_i \cdot a_i, \quad k_i \in \mathbb{Z}.$

也就是关于 $\{a_i\}_{i \in S}$ 的整数线性组合。

🧮 Note: 裴蜀定理（Bézout）： $\{a_i\}$ 的整数线性组合恰好覆盖 $\gcd(a_i : i \in S)$ 的全部整数倍。

所以走过点集 $S$ 的可达魔力值集合 $=$ $\gcd(a_i : i \in S)$ 的全体整数倍。目标 $V$ 可达 等价于 $\gcd(S) \mid V$ 。

殊途同归一句：经过一个点不强制喝它的药水，但跳过 $=$ 把它从计入 gcd 的集合里去掉，gcd 只会变大、整除关系只会更难满足。所以最优策略就是把走过的点全喝，状态干脆只追"目前路径上点的 gcd"一个量。

gcd 的状态数 $=$ $O(\log V)$

• 起点 gcd $= a_1$

• 每加入一个新点 $v$ ， gcd 变成 $\gcd(g, a_v)$ ：要么不变（ $a_v$ 是 $g$ 的倍数），要么至少缩小一半（变成 $g$ 的真因子）

从 $a_1$ 一路降到 $1$ 最多 $\log_2 a_1 = O(\log V)$ 步。出现过的 gcd 全是 $a_1$ 的因数，每个节点最多 $O(\log V)$ 种 gcd 状态。

关键不变量：状态空间上界 $n \cdot O(\log V) \approx 10^4 \cdot 30 = 3 \times 10^5$ ，分层图 Dijkstra 完全跑得动。

分层图 Dijkstra

状态 $(u, g)$ ：当前在节点 $u$ 、当前路径上点的 gcd 是 $g$ 。

转移：从 $(u, g)$ 沿边 $(u, v, w)$ 到 $(v, \gcd(g, a_v))$ ， dist 加 $w$ 。

起点 $(1, a_1)$ ， dist $= 0$ 。

答案：扫所有可达状态 $(u, g)$ ，其中满足 $V \bmod g = 0$ 的最小 dist 即为答案。

边权全正、状态空间有限，标准 Dijkstra（pq + lazy stale check）就够。

实现要点

• 用 vector<map<ll, ll>> mp(n+2) 存每个节点的 gcd → dist

• pq pop 出来 必须 先判 step > mp[u][gcd] 跳过 stale 态——否则同一个状态反复被 push 出来展开邻居，状态量爆炸 TLE

• 起点先特判 V % a_1 == 0 直接输出 0

• 找到 ans 后加剪枝 step + w >= ans continue

• ans 永远是 LLONG_MAX 时输出 -1 ——题面保证 $a_1$ 的质因数 $\subseteq V$ 的质因数，但不蕴含 $a_1 \mid V$ ，反例 $a_1 = 4, V = 18$ 下若所有 $a_i \in \{4, 8, 12, \dots\}$ 永远凑不出 $18$ ，必须返回 -1

AC 代码

AC 提交链接

展开完整 C++ 源码

// teamname: Gospel_rock
/**
 * Problem: Card
 * Contest: 2026 杭电春季联赛 7
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1203&pid=1001
 * Created: 2026-05-08 22:53:45
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct UStepGcd {
    ll u, gcd, step;
    bool operator<(const UStepGcd &o) const { return step > o.step; }
};

void Solve() {
    ll N, M, V;
    cin >> N >> M >> V;
    vector<ll> A(N + 2);
    vector<vector<array<ll, 2>>> g(N + 2);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= M; ++i) {
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    if (V % A[1] == 0) { cout << 0 << "\n"; return; }
    priority_queue<UStepGcd> pq;
    pq.push({1, A[1], 0});
    vector<map<ll, ll>> mp(N + 2);
    ll ans = LLONG_MAX;
    while (!pq.empty()) {
        auto [u, gcd, step] = pq.top();
        pq.pop();
        if (step > mp[u][gcd]) continue;
        for (auto [v, w] : g[u]) {
            ll to_gcd = __gcd(A[v], gcd);
            if (V % to_gcd == 0) ans = min(ans, step + w);
            if (step + w >= ans) continue;
            if (!mp[v].contains(to_gcd) || step + w < mp[v][to_gcd]) {
                mp[v][to_gcd] = step + w;
            } else {
                continue;
            }
            pq.push({v, to_gcd, step + w});
        }
    }
    if (ans == LLONG_MAX) { cout << -1 << "\n"; return; }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) Solve();
    return 0;
}

心路历程（TLE → WA → AC）

第一版 TLE

priority_queue + map<ll, map<ll, ll>> 直接交，TLE 。原因：

• pop 出来没做 stale check ，直接处理邻居 → 同一个 (u, g) 状态被反复 push、pop、展开邻居，pq 状态量指数膨胀

• map<ll, map<ll, ll>> 嵌套红黑树，每次 contains / operator[] 都是 O(log²) ，常数惨

修法：

1. pop 之后立刻 if (step > mp[u][gcd]) continue;

2. 外层换成 vector<map<ll, ll>> （节点下标天然是 vector 索引）

3. 顺手加 step + w >= ans 早剪枝

第二版 WA

修完 TLE 跑通样例，交上去 WA 。原因：

• ll ans = LLONG_MAX ，不可达时没转 -1 直接打印了 9223372036854775807

• 题面要求不可达输出 -1

修法：

cout << (ans == LLONG_MAX ? -1 : ans) << "\n";

题面"保证 $a_1$ 的质因数 $\subseteq V$ 的质因数"乍看像在保证可达，其实不蕴含 $a_1 \mid V$ ：例如 $a_1 = 4, V = 18$ ， $\{2\} \subseteq \{2, 3\}$ 满足前提，但 $4 \nmid 18$ 。如果整张图所有 $a_i$ 都是 $4$ 的倍数（gcd 永远是 $4$ 的倍数）就永远凑不出 $18$ ，必须返回 -1 。

加上这一行后 AC 。

附件

（暂无）