2015.9.11模拟赛 codevs 4160【会玩的】

题目描述  Description

hzwer真的很会玩啊…他有一个n*m的方格，每次可以给方格添加一整行或一整列，但是不能删除。现在他想要让总格子数超过k个，但是又想让总格子数尽可能小。请找出这时的n,m。如果有多解，输出任意一种方案。

 

输入描述  Input Description

一行3个数n,m,k。

输出描述  Output Description

第一行一个数ans,表示此时的方格数。

第二行两个数m’,n’,表示此时的行数列数。如果有多解，输出任意一种方案

样例输入  Sample Input

3 5 18

 

样例输出  Sample Output

18

3 6

 

数据范围及提示  Data Size & Hint

对于100%数据，1<=m,n<=10^9,1<=k<=10^12.

 

题意是给定n,m,k,要求找到a>=n,b>=m,使得a*b>=k且a*b最小。如果有多解，输出a,b字典序最小的方案。

n*m>=k时，可以直接退出

否则n*m<k

考虑固定一个数a,则另一个数最小是k/a.那么可以用（a,k/a）来更新答案。
如果枚举a,那么只要到sqrt(k)即可。因为我们从1到a枚举，如果有k/a<a，那么一定k/a已经被枚举过。这个状态就没有意义了

因此一个一个for到sqrt(k)即可

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define LL long long
using namespace std;
LL n,m,k;
bool rev;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    n=read();m=read();k=read();
    if (n>m)swap(n,m),rev=1;
    if (n*m>=k)
    {
        printf("%lld\n%lld %lld",n*m,n,m);
        return 0;
    }
    while (1)
    {
        bool mrk=0;LL a=0;
        for (int i=n;i<=sqrt(k);i++)
          if (k%i==0&&k/i>=m)
          {
              mrk=1;
              a=i;
              break;
          }
        if (mrk)
        {
            if (!rev)printf("%lld\n%lld %lld",k,a,k/a);
            else printf("%lld\n%lld %lld",k,k/a,a);
            return 0;
        }else k++;
    }
}