Codeforces Round #613 (Div. 2) C. Fadi and LCM (数学)

2024-09-05 07:02:20

题意:给你一个正整数\(x\),找两个正整数\(a\),\(b\),使得\(lcm(a,b)=x\),并且\(max(a,b)\)最小.
题解:我们知道,\(lcm(a,b)=a*b/gcd(a,b)\),所以如果\(a\)和\(b\)不互质,那么\(a*b\)必然可以约去一个\(gcd(a,b)\),也就表示\(max(a,b)\)的值可以变得更小,所以我们要找的\(a\)和\(b\)必然要互质,即得到\(gcd(a,b)=1\),从而推出\(a*b=x\),所以我们可以直接枚举到\(\sqrt{x}\),更新最小值即可.

代码:

ll x;

ll ans1,ans2,res=1e18;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>x;

    for(ll i=1;i*i<=x;++i){

        if(x%i) continue;

        if(__gcd(i,x/i)==1 && res>max(i,x/i)){

            ans1=i,ans2=x/i;

        }

    }

    cout<<ans1<<' '<<ans2<<endl;

    return 0;

}

最新文章

热门文章