题解：P11275 微观戏剧

封面

思路：

数学题。

当 xx 等于 yy 时，从 xx 到 yy 最少只要 00 步。

当 xx 不等于 yy 时，从 xx 到 yy 最少需要的步数要分两种情况考虑：

  1. 直接过去，步数为 lcm⁡(x,y)\operatorname{lcm}(x,y)。
  2. 通过最大公因数过去，步数为 lcm⁡(x,gcd⁡(x,y))+lcm⁡(y,gcd⁡(x,y))\operatorname{lcm}(x,\gcd(x,y))+\operatorname{lcm}(y,\gcd(x,y))。

答案为两种情况里的最小值。

考虑到 long long 范围不够，所以用 __int128。

代码：

#include<bits/stdc++.h>
using namespace std;
#define itn int
#define ull unsigned long long
__int128 x,y;
__int128 read(){
    bool f=1;__int128 x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=(f?x:-x);
	return x;
}
void write(__int128 x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
    return;
}
__int128 __lcm(__int128 x,__int128 y){
	return x/__gcd(x,y)*y;
}
int main(){
	int q;
	cin>>q;
	while(q--){
		x=read();y=read();
		if(x==y)cout<<0<<"\n";
		else{
			__int128 g=__gcd(x,y);
			__int128 ans1=__lcm(x,g)+__lcm(y,g),ans2=__lcm(x,y);
			write(min(ans1,ans2));
			cout<<"\n";
		}
	} 
	return 0;
}