2020WHU校赛 I - Interesting Matrix Problem（规律+整除分块）
传送门
先放出题解的PPT：
考虑二分答案。因为小于等于
k
k
k的数他们的因子一定出现在坐标
(
i
,
j
)
(i,j)
(i,j)中，设
f
(
x
)
f(x)
f(x)为
x
x
x的因子个数，因为是成对出现的，实际上在矩阵中
x
x
x的个数就是因子的个数。那么就是求
∑
i
=
1
k
f
(
i
)
\sum_{i=1}^kf(i)
∑i=1kf(i)，不难发现这个式子其实就是整除分块，那么就套个板子求就行了，题解上说有边界需要处理，但是不处理也能过，可能和
k
≤
m
a
x
(
n
,
m
)
k\leq max(n,m)
k≤max(n,m)有关
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=998244353;
const int maxn=2e5+10;
ll n,m,q,k;
bool check(ll x){
ll ans=0;
for(ll l=1,r;l<=min(n,x);l=r+1){
r=x/(x/l);
ans+=(x/l)*(r-l+1); //不少人这里写的是min(x/l,m)，但x/l不可能大于m的好吧
}
return ans>=k;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
n=min(n,m);
m=max(n,m);
while(q--){
cin>>k;
ll l=1,r=m,ans;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}else l=mid+1;
}
cout<<ans<<endl;
}
return 0;
}