D 牛牛与整除分块

题意：T组测试数据，每组给出整数N和X，询问在集合 中，是第几大元素。

首先注意到数据范围。因此如果每次询问，都将每个数的集合S算出来，复杂度是的，必然超时，因此每次询问应该是或者 才能符合要求。
进行打表找规律，以下给出大约50个数的打表结果。

引号左边分别是数和集合S的个数，右边是集合S里有什么数。
很直观的发现两个规律。①：集合S由两部分组成。左半部分是一个差为1的等差数列1,2,3....k，并且这一部分的数与右边的数有对应关系②集合S所含有的数的个数是成规律增长的。
先看第一个规律。S的左半部分是一个等差数列，那么和右半部分的分界点k在哪里呢？观察得到，。
因此在询问S左半部分数是第几大的时候，只需要知道S的大小，用S的大小去减他即可。
同时左半部分的数和右半部分的数是沿中心有对应关系。
距离。如16：1 2 3 4 5 8 16，，，。
因此在询问S右半部分数是第几大的时候，我只需要知道他对应的元素是多少即可。
因此，假如我询问16是第几大，我只要通过找到n除x对应的元素1，那他必然是最大。同理询问8的时候，找到对应的元素是2，那他必然是第二大。

接下来就只有最后一个问题了，如何快速找到集合S有多少个数？

在第一个规律中我们发现S的分界点是，虽然不一定有关联，但是也会下意识的寻找有没有对应的关系。
观察图我们发现，N正好是k的平方数，也就是的时候，S的数量一定会加一。
其次，虽然S数量增加时不一定N是平方数，但是平方数的上下区间间隔是相等的，并且正好等于k。比如平方数25的上下，S的数量为8和9的区间间隔都是5。
同时，平方数所在的区间S的数量为 。
因此，我们只要找到对应数N的上一个平方数，然后判断和这个平方数的距离，就可以知道他是属于上一个平方数的上下区间还是下一个平方数的上下区间了。
代码如下

#include <bits/stdc++.h>
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll read(){ll f=1;ll x=0;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f; }
inline ll quick_pow(ll a,ll b,ll mod) {ll ans=1,base=a;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 1e9 + 7;
const ll maxn = 100000 + 10;
using namespace std;

int main()
{
    BUFF;
    int T;
    cin>>T;
    while(T--)
    {
        ll n, x;
        ll num;
        cin >> n >> x;
        ll sq = (ll)sqrt(n);
        if(n - sq*sq >= sq)
            num = sq * 2;
        else
            num = sq * 2 - 1;
        if(n/x < sq)
        {
            cout << num - n / x + 1 << '\n';
        }
        else
            cout << x << '\n';
    }

    return 0;
}