牛客网国庆集训派对Day5 题目 2018年

链接：https://www.nowcoder.com/acm/contest/205/L
来源：牛客网
参考博客：https://blog.csdn.net/HTallperson/article/details/82943889

数论之神

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

终于活成了自己讨厌的样子。

这是她们都还没长大的时候发生的故事。那个时候，栗子米也不需要为了所谓的爱情苦恼。
她们可以在夏日的午后，花大把的时间去研究生活中一些琐碎而有趣的事情，比如数论。
有一天西柚柚问了栗子米一个题，她想知道中有多少不同的数，这些不同的数字里面第k大的是多少。

输入描述:

第一行一个整数T(T≤ 10

)，表示数据组数。
每组数据第一行两个整数，表示n,k(1≤ n≤ 10

)，保证k不会超过不同的数字个数。

输出描述:

对于每组数据输出，输出两个整数，表示有多少个不同的数字和这里面第k大的是多少。

示例1

输入

3

1 1

5 2

67 8

输出

1 1

3 2

15 8
思路：整除分块，O（根号n）。找到出现连续相同的n/i的分界点（就是根号n处）。
代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int inf=0x3f3f3f3f;

 const long long mod=;

 typedef long long ll;

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         ll n,k;

         scanf("%lld %lld",&n,&k);

         ll s=sqrt(n);

        ll ans1,ans2;

         if(s*(s+)<=n)

         {

              ans1=*s;

         }

         else

         {

              ans1=*s-;

         }

         if(k==)

         {

             ans2=n;

         }

         else if(k<=s)

         {

             ans2=n/k;

         }

         else ans2=ans1-k+;

         printf("%lld %lld\n",ans1,ans2);

     }

     return ;

 }