Solution #

It’s quite obvious that $a$ and $b$ must be coprime. Now let’s prime factorize $X$ and there will be at most 11 distinct primes since the product of the first 12 primes is greater than $1\cdot 10^{12}$ . To find the answer we can simply distribute them between $a$ and $b$ with bruteforce.

Another solution is loop over all divisors $d$ of $X$ , check if $\gcd(d,\frac X d)$ is 1 and minimize the answer.

Code #

Prime factorization:

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define pb push_back
 
using namespace std;
 
typedef long long ll;
const ll INF = 1e12;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	ll x;
    cin>>x;
    vector<ll> vec;
    for(ll f=2;f*f<=x;f++){
        ll tmp=1;
        while(x%f==0){
            tmp*=f;
            x/=f;
        }
        if(tmp!=1) vec.pb(tmp);
    }
    if(x>1)vec.pb(x);
    ll aa=INF,ab=INF;
    for(ll i=0;i<(1<<vec.size());i++){
        ll a=1,b=1;
        forn(j,vec.size()){
            if((i&(1<<j))>0) a*=vec[j];
            else b*=vec[j];
        }
        if(max(a,b)<max(aa,ab)){
            aa=a;
            ab=b;
        }
    }
    cout<<ab<<' '<<aa;
    return 0;
}

Looping factors:

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const ll INF=1e15;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	ll x;
    cin>>x;
    ll ansa=INF,ansb=INF;
    for(ll f=1;f*f<=x;f++){
        if(x%f==0){
            if(__gcd(f,x/f)==1){
                if(x/f<ansb){
                    ansa=f;
                    ansb=x/f;
                }
            }
        }
    }
    cout<<ansa<<' '<<ansb;
    return 0;
}

Solution for Codeforces 1285C - Fadi and LCM

Solution #

Code #