Solution #
It’s quite obvious that and must be coprime. Now let’s prime factorize and there will be at most 11 distinct primes since the product of the first 12 primes is greater than . To find the answer we can simply distribute them between and with bruteforce.
Another solution is loop over all divisors of , check if 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;
}