题解：P14079 [GESP202509 八级] 最短距离

lcfollower · 2025-09-30 14:14:41 · 题解

Update

• 修改一处笔误（错误），删除最开头的话。

Solution

首先我们记录 g = \gcd(a ,b)。

观察到 1\le a ,b\le 10^9，但是 N = 10^{18}，一开始我很奇怪。

然后我们思考，对于一条边的情况，我们先记当前答案为 ans：

然后我们考虑多条边的情况。

如果 g = 1，我们有：

• 取 k 为 lcm(a,b) 的倍数，那么代价为 cost(a ,k) + cost(b,k) = 2q。

• 取 a\mid k，b\not| \ k，代价为 p + q，明显高于 p。

• 取 a\not | \ k，b\mid k 同理，代价为 p + q。

• 取 a\not |\ k，b\not | \ k，那么代价为 2p，明显不如 p。

• 显然取三个点及以上时，代价都比 2q 或者 p 高。

• 因此答案为 \min\{p ,2q\}。

如果 g \neq 1，则有：

• 取 k 为 lcm(a,b) 的倍数，那么代价为 cost(a ,k) + cost(b,k) = 2q，明显代价高于 q。

• 取 a\mid k，b\not| \ k，代价为 p + q，明显高于 q。

• 取 a\not | \ k，b\mid k 同理，代价为 p + q。

• 取 a\not |\ k，b\not | \ k，那么代价为 2p。

• 显然取三个点及以上时，代价都比 2p 或者 q 高。

• 因此答案为 \min\{q ,2p\}。

这两种情况是类似的哦。

然后有一些特殊情况：

:::success[实现]{open}

namespace lolcrying {

    inline int gcd(int n ,int m) {return !m ? n : gcd(m ,n % m) ; }

    signed main () {

        int n = read() ,m = read() ,ans = 0;
        int g = gcd(n ,m);

//就是个分类讨论。

        if(n == m) ans = 0;
        else if(min(n ,m) == 1) ans = p;
        else if(g == 1) ans = min(2 * q ,p);
        else ans = min(2 * p ,q);

        writeln(ans);

        return 0;
    }
}

:::