CF1916B Two Divisors

One_JuRuo · 2023-12-31 12:26:09 · 题解

思路

看到题目要求求一个数 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;
}