手机(mobile phone)

DD 想买一个新手机,这个手机的长为 \(x\) ,宽为 \(y\) ,大小等于 \(n(x*y=n)\) ,她喜欢用正方形的袋子装手机,所以她希望最小化这个手机长边的长度\((\max(x,y))\),请问在长边最小的情况下这个手机的长宽分别是多少?

输入格式
一个整数表示 \(n\)

输出格式
输出这个手机的长\((\max(x,y))\),宽\((\min(x,y))\)

数据范围
对于 \(30\%\) 的数据,\(1 \leq n \leq 100\)

对于 \(60\%\) 的数据,\(1 \leq n \leq 10000\)

对于 100% 的数据,\(1 \leq n \leq 10^{12}\)
输出时每行末尾的多余空格,不影响答案正确性

样例输入

6

样例输出

3 2

其实就是求因数,要求大的那个因数尽量小。考虑枚举所有因数,然后找一个最大值。因数成对出现,我们知道一个就知道另一个。所以\(O(\sqrt(n))\)枚举即可。

#include <bits/stdc++.h>
using namespace std;
long long n;
long long x,y;
int main()
{
//    freopen("mobile.in", "r", stdin);
//    freopen("mobile.out", "w", stdout);
    cin>>n;
    for(int i=1;i<=min(n,1000000LL);i++)
    {
        if(i>n/i)
            break;
        if(n%i==0)
        {
            x=i,y=n/i;
        }
    }
    cout<<y<<' '<<x<<endl;
    return 0;
}
————————

DD wants to buy a new mobile phone. The length of this mobile phone is \ (x \), the width is \ (Y \), and the size is equal to \ (n (x * y = n) \). She likes to put the mobile phone in a square bag, so she wants to minimize the length of the long side of this mobile phone \ (\ max (x, y)) \). What are the length and width of this mobile phone when the long side is the smallest?

Input format
An integer represents \ (n \)

Output format
Output the length \ (\ max (x, y)) \) and width \ (\ min (x, y)) \) of this mobile phone

Data range
For data of \ (30 \% \), \ (1 \ Leq n \ Leq 100 \)

For data of \ (60 \% \), \ (1 \ Leq n \ Leq 10000 \)

For 100% data, \ (1 \ Leq n \ Leq 10 ^ {12} \)
The extra space at the end of each line during output will not affect the correctness of the answer

sample input

6

sample output

3 2

In fact, it is to find the factor, and the factor that is required to be large shall be as small as possible. Consider enumerating all factors and then finding a maximum. Factors appear in pairs. We know one and we know the other. So \ (O (\ sqrt (n)) \) enumeration is enough.

#include <bits/stdc++.h>
using namespace std;
long long n;
long long x,y;
int main()
{
//    freopen("mobile.in", "r", stdin);
//    freopen("mobile.out", "w", stdout);
    cin>>n;
    for(int i=1;i<=min(n,1000000LL);i++)
    {
        if(i>n/i)
            break;
        if(n%i==0)
        {
            x=i,y=n/i;
        }
    }
    cout<<y<<' '<<x<<endl;
    return 0;
}