题目
分析
假设答案为ans，
发现$$k=sum_{i=1}^{min(n,k)}lfloor dfrac{ans}{i}
floor$$
于是可以对ans进行二分，
用分块来求出上面的式子。与k进行比较。
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
const int maxlongint=2147483647;
const int mo=1e9+7;
const int N=100005;
using namespace std;
int n,m,q,k;
int min(int x,int y)
{
return x<y?x:y;
}
long long get(int x)
{
int last=0,mn=min(n,x);
long long sum=0;
for(int i=1;i<=mn;i=last+1)
{
last=min(n,x/(x/i));
sum+=(1ll*x/i)*1ll*(last-i+1);
}
return sum;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(;q--;)
{
scanf("%d",&k);
if(n>m) swap(n,m);
if(k==0) printf("0
");
int l=1,r=k;
while(l<r)
{
int mid=(l+r)>>1;
long long cnt=get(mid);
if(cnt==k) l=r=mid;
else
if(cnt>k) r=mid;
else l=mid+1;
}
printf("%d
",l);
}
}