P10858 [HBCPC2024] Long Live 题解

Cyx20110930 · 2024-08-12 09:58:49 · 题解

简要题意

输入 x,y，找到乘积最大的两个数 a,b 使得 a\sqrt{b} = \sqrt{\frac {lcm(x,y)} {gcd(x,y)}}。

Sol

一看，这不可以秒杀吗？

因为 \sqrt{\frac {lcm(x,y)} {gcd(x,y)}} 是定值，所以题目变为 a\sqrt{b} 是定值时，a\times b 最大。

易得 a\times b=\frac{(a\sqrt{b})^2}a，分子不变，所以要让分母最小，得数最大，即 a 最小为 1。

Code

十年 OI 一场空，不开 long long 见祖宗！

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int gcd(int a,int b) 
{    
    return b>0 ? gcd(b,a%b):a;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x,y;
        cin>>x>>y;
        cout<<"1 "<<(x*y/gcd(x,y))/gcd(x,y)<<endl;
    }
}