题解：P10858 [HBCPC2024] Long Live

x1489631649 · 2024-08-11 19:50:26 · 题解

题目链接

输入

多组数据，每组数据两个整数 x,y(1 \le x,y \le 10^9)。

输出

最小公倍数除以最大公因数开根号然后找到两个数 a 与 b ，将 b 的开根号在乘 a 等于那个数，且使得 a \times b 的积最大。

分析

1. 首先我们将等式两边同时平方可得最小公倍数除以最大公因数等于 a^2 \times b。
2. 转移使得 a \times b 等于最小公倍数除以最大公因数与 a 的乘积。由于最小公倍数和最大公因数已经确定，所以只需要让 a 尽量小，而 a 的最小值只能是 1。

   实现

   我们可以使用系统自带的函数 \gcd 来进行求值然后再用最小公倍数乘最大公因数等于两个数的积来求出最小公倍数。

   Code

   #include<bits/stdc++.h>
   using namespace std;
   int main()
   {
   unsigned long long t,x,y,flag;
   cin>>t;
   while(t--)
   {
       cin>>x>>y;
       if(x>y)
           swap(x,y);
       cout<<"1 "<<(x*y/__gcd(x,y))/__gcd(x,y)<<endl;
   }
   } 

   时间复杂度

   时间复杂度为 O(t\log V)，其中 V 是值域，显然可以通过。