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

Update

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

Solution

• $g = 1$，$ans = p$。
• $g\neq 1$，$ans = q$。

• 取 $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\}$。

• 取 $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\}$。

• $a = b$，$ans = 0$。
• $\min\{a ,b\} = 1$，不能按照上面的讨论，举个例子很显然，然后我们发现任意一种代价都高于 $p$，因此 $ans = p$（留给读者自己分类讨论）。

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;
	}
}