long long 开小了，血的教训。

题解 #

不难看出 $a$ 和 $b$ 必须是互质的，我们质因数分解 X，最多有 11 个不同的质因数因为前 12 个质因数的积大于 $1\cdot 10^{12}$ 。我们可以暴力枚举所有的分配情况来得到最优的答案。

另一种解法是遍历 X 的所有因数 $p$ 然后判断 $\gcd(d,\frac X d)$ 是否是 1 并更新答案。

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;
}

Codeforces 1285C - Fadi and LCM 题解

题解 #

Code #