51Nod-3045 Lcm与Gcd构造 题解

Lcm与Gcd构造

题目概述

已知gcd(a,b)和lcm(a,b)，求满足条件的ab使得a+b最小

思路分析

根据$gcd$和$lcm$可以求得$a*b=gcd*lcm$
然后枚举$a*b$的因子分别作为$a$和$b$，判断是否满足条件并求最小值
实际复杂度过大，所以这里采用另外的方式
令$x=\frac{a}{gcd}$，$y=\frac{b}{gcd}$
则$a + b = gcd * (x + y)$，$gcd(x, y) == 1$
$x * y = \frac{a * b}{gcd * gcd} = \frac{lcm}{gcd}$

只需要枚举$\frac{lcm}{gcd}$因子即可

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
const int N = 2e5 + 5;
const int MOD = 1e9 + 7;
llong gcd, lcm;

int main() {
    #ifdef LOCAL
        freopen("D:/Code/ACM/in.in", "r", stdin);
        freopen("D:/Code/ACM/out.out", "w", stdout);
    #endif
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;	cin >> T;
    while (T--) {
        cin >> gcd >> lcm;
        llong t = lcm / gcd;
        llong ans = 0x7fffffffffffffff;
        for (llong i = 1; i <= t / i; i++) {
            if (t % i == 0 && __gcd(i, t / i) == 1) {
                ans = min(ans, gcd * (i + t / i));
            }
        }
        cout << ans << "\n";
    }
    return 0;
}