[P14079]最短距离-题解

本题需要分类讨论，共3种情况：
1.a,b互质。此时我们明显能想到输出p，但要是q比p小很多，还真不一定。我们推一下，容易想到以a*b作为桥梁，这样，代价就是2q。输出p与2q之间小的那个即可。千万要注意，当a,b之间有一个是1的时候，一定要输出p！
2.a,b不互质。同理，输出q与2p之间小的那个即可。
3.一定不要忘了a=b的时候输出0！

CPP

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,p,q;
	cin>>n>>p>>q;
	while(n--)
	{
		int a,b;
		cin>>a>>b;
		if(a==b)
		{
			cout<<0<<endl;
			continue;
		}
		if(__gcd(a,b)==1)
		{
			if(a==1||b==1)
			{
				cout<<p<<endl;
			}
			else
			{
				cout<<min(p,2*q)<<endl;
			}
		}
		else
		{
			cout<<min(q,2*p)<<endl;
		}
	}
	return 0;
}

[P14079]最短距离-题解

文章操作

相关推荐

评论

[P14079]最短距离-题解