牛客国庆集训派对Day5 数论之神

题目描述

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

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

输入描述:

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

⁵

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

¹⁸

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

输出描述:

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

示例1

输入

输出

1 1
3 2
15 8

题意：求整除这个数之后的所有不同数的第k大
思路：除法分块有个规律，就是你前sqrt（n）个数肯定除数都是不相同的，所有我们前面sqrt（n）这一段可以直接算出来，
如果k<=sqrt(n)的话，那么直接答案就是n/k；

比如16
16 8 5 4 3 2 2 2 1 1  1  1  1  1  1  1
1  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
可以看出sqrt(n)前面的n个数都不相同，然后剩下的不同的个数就是n/(sqrt（n）+1)的个数
所以总共的个数就有sqrt(n)+n/(sqrt(n)+1)个

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n,k;
        scanf("%lld%lld",&n,&k);
        ll a=sqrt(n);
        ll ans1,ans2;
        ans1=a+n/(a+1);
        if(k<=a) ans2=n/k;
        else{
            n=n/(a+1);
            ans2=n-(k-a)+1;
        }
        printf("%lld %lld
",ans1,ans2);
    }
}