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

这题一看就是要 $O ( \log{a} )$ 以内出结果的题！！！ （~~别问我怎么知道的）~~。

本题就是说对于两个数

a

和

b

, 若

gcd(a, b) = 1

, 则连一条边权为

p

的边，否则连一条边权为

q

的边。问

a

和

b

的最短路。

我们分两种情况讨论：

当 $gcd(a, b) = 1$ 时， $ans$ 可以等于 $p$ ，也可以等于 $2 \times q$ , 因为可以先从点 $a$ 到点 $a \times b$ ，再从点 $a \times b$ 到点 $b$ 。
当 $gcd(a, b) > 1$ 时， $ans$ 可以等于 $q$ ，也可以等于 $2 \times p$ , 因为可以先从点 $a$ 到点 $1$ ，再从点 $1$ 到点 $b$ 。

但是还要特判一下！！！

当

a = b

时，

ans = 0

。

当

a = 1

或

b = 1

时，

ans = p

。

以上就是正解思路了。

时间复杂度

O ( n \log{a} )

, 可以通过本题。

空间复杂度

O ( 1 )

, 包可以通过本题的。

最后， 你们最爱的代码来了！！！

CPP

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int n;
LL ans, p, q, a, b, g;
int main() {
	scanf("%d%lld%lld", &n, &p, &q);
	while(n --) {
		ans = 1e18;
		scanf("%lld%lld", &a, &b);
		if(a == b) {
			puts("0");
			continue;
		}
		if(a == 1 || b == 1) {
			printf("%lld\n", p);
			continue;
		}
		g = __gcd(a, b);
		if(g == 1) ans = min(p, q * 2);
		else ans = min(q, p * 2);
		printf("%lld\n", ans);
	}
	return 0;
}

代码很简单，按上面的思路做就行。

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

文章操作

相关推荐

评论

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