I-Interesting Matrix Problem 二分+分块

I-Interesting Matrix Problem

题意：给你N *M的矩阵 （1<=N , M <=1e8）矩阵内的值是 i乘j 现有q次询问，每次询问输入k 代表 查询这个矩阵内第k小的数是多少。

做法：第一思路二分答案，然后mid去check O(N) 枚举行 i 计算mid/i的个数，发现会超时

写下公式：

这个公式好眼熟啊，不就是数论的整除分块，果断套了一个分块 时间复杂度：q*sqrt(N)

注意还要判断mid/i 不能大于m

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll n,m,q,k;
int valid(ll mid)
{
    ll ans=0;
    ll l,r;
    for(l=1;l<=mid;l=r+1){
        r=mid/(mid/l);

        ll t=mid/l;
        t=min(t,m);

        ans+=(1ll*r-l+1)*t;
    }
    return ans>=k;
}
void solve()
{
    scanf("%lld%lld%lld",&n,&m,&q);
    if(n>m) swap(n,m);
    while(q--){
        scanf("%lld",&k);


        ll l=1,r=m,ans;
        while(l<=r){
            ll mid=l+r>>1;
            if(valid(mid)) {
                ans=mid,r=mid-1;
                //printf("midmid:%lld\n",mid);
            }
            else l=mid+1;
        }
        printf("%lld\n",ans);
    }
}
int main()
{
    solve();
}