GCD and LCM

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define int long long

int gcd(int a, int b) {
    int c;
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}


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



using namespace std;

pair <int, int> subset_mul(const vector<int>& nums, int n, int ss){
    pair<int, int> t;
    t.first = 1;
    t.second = 1;
    int d = ss - nums[0];
    int r = nums[0];
    int m = 1;
    if (n == 0){
        return t;
    }
    for (int i = 1; i < (1ll<<n); i++) {
        int curr=1;
        for (int j = 0; j < n; j++) {
            if((1ll<<j)&i) curr*=nums[j];
        }
        if (d >= abs(ss - curr)) {
            d = abs(ss - curr);
            r = curr;
        }
        m = max(m, curr);
    }
    t.first = r;
    t.second = m;
    return t;
}

vector<int> factors(int n) {
    vector<int> f;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            f.push_back(i);
            n /= i;
            while (n % i == 0) {
                f[f.size() - 1] *= i;
                n /= i;
            }
        }
    }
    if (n != 1) {
        f.push_back(n);
    }
    // cout << "hehe" << endl;
    // for (int i = 0; i < f.size(); i++) {
    //     cout << f[i] << " ";
    // }
    // cout << "hehe" <<  endl;
    return f;
}

signed main() {
    int a, b, g, l, h;
    cin >> a >> b;
    g = gcd(a, b);
    l = lcm(a, b, g);
    h = l / g;
    vector<int> f = factors(h);
    pair<int, int> t = subset_mul(f, f.size(), sqrt(h));
    int x, y;
    // cout << g << endl;
    // cout << l << endl;
    // cout << t.first << " " << t.second << endl;
    x = g * t.first;
    y = g * (t.second / t.first);
    // cout << x << " " << y << endl;
    cout << min(x, y) << " " << max(x, y) << endl;

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: TIME LIMIT EXCEEDED

Test 44

Verdict: TIME LIMIT EXCEEDED

Test 45

Verdict: TIME LIMIT EXCEEDED

Test 46

Verdict: TIME LIMIT EXCEEDED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: TIME LIMIT EXCEEDED

Test 58

Verdict: TIME LIMIT EXCEEDED

Test 59

Verdict: TIME LIMIT EXCEEDED

Test 60

Verdict: ACCEPTED