自动搬运

查看原文

来自洛谷，原作者为

	Vct14 **

搬运于2025-08-24 23:02:02，当前版本为作者最后更新于2024-08-11 22:03:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解代码没有分讨？我来交一发！

本场比赛最难的签到题。

题意：将整数 $x$ 变为整数 $y$ 代价为 $\operatorname{lcm}(x,y)$，求将 $a$ 变为 $b$ 的最小代价。注意：只能变为大于 $1$ 的整数。

先讨论两种简单的情况。

如果 $a=b$，则最小代价为 $0$。不动即可。

否则如果 $a\mid b$，则一次变化最优，最小代价为 $b$，否则若变化多次，最后一步的代价一定大于或等于 $b$。

否则如果 $\gcd(a,b)\ne1$。

若走一步，代价 $\operatorname{lcm}(a,b)$。

否则因为 $\operatorname{lcm}(x,y)\geqslant x$，第一步的代价一定大于或等于 $a$，最后一步的代价一定大于或等于 $b$，理论最小代价 $a+b$，要实现这个代价只能走两步。设途经的数为 $z$，第一步走需使得 $\operatorname{lcm}(a,z)=a$，第二步走需使得 $\operatorname{lcm}(z,b)=b$。即 $z$ 是 $a,b$ 的公因数，可以走 $a\to \gcd(a,b)\to b$ 实现。

设 $\gcd(a,b)=d,a=dx,b=dy,(x,y)=1$。则 $a+b=d(x+y)$，$\operatorname{lcm}(a,b)=dxy$。由于 $a<b$ 且 $a\nmid b$，有 $1<x<y,(x,y)=1$，因此 $(x-1)(y-1)>1$，即 $xy>x+y$。所以 $\operatorname{lcm}(a,b)>a+b$。最小代价为 $a+b$。

只剩下 $\gcd(a,b)=1$ 的情况。这种情况我们是走不到 $\gcd(a,b)$ 的。

如果走一步，代价 $\operatorname{lcm}(a,b)=ab$。

如果走多步，因为互质的两数的最小公倍数是它们的乘积，为了使代价尽量小，我们可以选择途经 $a$ 和 $b$ 的最小质因子 $\operatorname{minp}(a)$ 和 $\operatorname{minp}(b)$ 使乘积尽量小。

若途经的数 $z$ 与起点 $a'$ 和终点 $b'$ 都互质，代价为 $a'z+b'z$，我们可以选择途经 $2$ 使得代价最小。

整理一下最终情况。设 $p=\operatorname{minp}(a),q=\operatorname{minp}(b)$。

1. $a\to b$，代价 $ab$。
2. $a\to2\to b$，代价 $\operatorname{lcm}(a,2)+\operatorname{lcm}(b,2)$。
3. $a\to p\to b$，代价 $\operatorname{lcm}(a,p)+\operatorname{lcm}(p,b)=a+pb$。
4. $a\to q\to b$，代价 $\operatorname{lcm}(a,q)+\operatorname{lcm}(q,b)=aq+b$。
5. $a\to p\to 2\to b$，代价 $\operatorname{lcm}(a,p)+\operatorname{lcm}(p,2)+\operatorname{lcm}(b,2)=a+\operatorname{lcm}(p,2)+\operatorname{lcm}(b,2)$。
6. $a\to 2\to q\to b$，代价 $\operatorname{lcm}(a,2)+\operatorname{lcm}(q,2)+\operatorname{lcm}(q,b)=\operatorname{lcm}(a,2)+\operatorname{lcm}(q,2)+b$。
7. $a\to p\to q\to b$，代价 $\operatorname{lcm}(a,p)+\operatorname{lcm}(p,q)+\operatorname{lcm}(q,b)=a+pq+b$。
8. $a\to p\to2\to q\to b$，代价 $\operatorname{lcm}(a,p)+\operatorname{lcm}(p,2)+\operatorname{lcm}(q,2)+\operatorname{lcm}(q,b)=a+\operatorname{lcm}(p,2)+\operatorname{lcm}(q,2)+b$。

以上代价取最小值即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long

int lcm(int a,int b){
	return a/__gcd(a,b)*b;
}

int mnp(int a){
	for(int i=2; i*i<=a; i++) if(!(a%i)) return i;
	return a;
}

signed main(){
	int t;cin>>t;
	while(t--){
		int a,b;cin>>a>>b;
		if(a==b){
			cout<<0<<"\n";
			continue;
		}
		if(!(b%a)){
			cout<<b<<"\n";
			continue;
		} 
		if(__gcd(a,b)!=1){
			cout<<a+b<<"\n";
			continue;
		}
		int p=mnp(a),q=mnp(b);
		int a2=lcm(a,2),b2=lcm(2,b),p2=lcm(2,p),q2=lcm(2,q);
		cout<<min({a*b,a+p*b,a*q+b,a2+b2,a+p2+b2,a2+q2+b,a+p*q+qb,a+p2+q2+b})<<"\n";
	}
	return 0;
}

写晕了/yun，如果哪里有问题欢迎在评论区指出。