CSES - Aalto Competitive Programming 2024 - wk12 - Mon - Results
Submission details
Task:GCD and LCM
Sender:aalto2024m_002
Submission time:2024-11-25 17:55:32 +0200
Language:C++ (C++20)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:81:48: error: 'sqrt' was not declared in this scope
   81 |     pair<int, int> t = subset_mul(f, f.size(), sqrt(h));
      |                                                ^~~~

Code

#include <iostream>
#include <vector>
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;
}