CF1916B Two Divisors

思路

看到题目要求求一个数 \(x\)，满足它的最大的两个因数分别是 \(a\) 和 \(b\)，并且规定一个数本身不是他的因数。

首先 \(x\) 需要是 \(a\) 和 \(b\) 的倍数，所以想到最小公倍数，如果不考虑最小公倍数等于 \(b\)，最小公倍数就一定是答案，因为最小公倍数是最小的满足是 \(a\) 和 \(b\) 倍数的数了，其他的答案都一定是最小公倍数乘以一个数 \(k\)，但是这样，\(a\times k\) 和 \(b\times k\) 就比原来的大，一定不是答案。

所以如果最小公倍数不是答案，就没有答案了，而题目又保证了存在答案，所以这种情况最小公倍数就是答案。

再考虑有些情况会导致最小公倍数等于 \(b\)，也就是 \(a\) 是 \(b\) 的因数。考虑到答案一定是 \(b\) 的倍数，所以考虑答案是 \(b\) 乘以几，首先如果是随便的一个 \(k\)，那么会导致 \(a\times k\) 大于 \(a\)，使得 \(a\) 不是次大的因数，所以我们考虑让 \(a\times k=b\)，这样才可能让 \(a\) 成为次大因数，所以答案就是 \(b\times \frac b a\)。同样的，如果这个答案不合法，就不可能存在其他答案合法，题目又保证一定存在答案，所以这个答案正确。

AC code

#include<bits/stdc++.h>
using namespace std;
long long T,a,b,gc;
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld",&a,&b),gc=__gcd(a,b),a/=gc,b/=gc,b*=a;//此时，b是最小公倍数除以最大公因数
		if(a==1) b*=b;//如果b是a的倍数，那么答案需要额外乘以b/a
		printf("%lld\n",b*gc);//记得把最大公因数乘回去
	}
	return 0;
}