E的非主流做法(
首先有一个结论：凑不出来的数形如 i*a-j*b 其中 i<b、j>0、i*a-j*b>0
二分答案，考虑大于等于 mid 的数中，有多少个凑不出来的
我们可以枚举i，计算使得 i*a-j*b>=mid 的 j 有多少个
有个比较有用的显然的优化：如果当前已经有大于等于 k 个这样的数了，就不用继续枚举 i 了
另一个比较有用的显然的优化：我们取 a>b
借助这两个优化，我们可以证明，单次check的复杂度是 sqrt(k) ，证明如下：
对于同一个 mid ， i 取 x+1 时符合条件的 j 至少比 i 取 x 时多 1 个，所以我们枚举 y 个 i 时，至少会得到 y2/2 个 j
所以我们每次check最多只需要枚举 sqrt(k) 个 i
总时间复杂度 o(log(a*b)*sqrt(k)) ，(跑的飞快
#include<bits/stdc++.h>
using namespace std;
long long a,b,k;
bool ok(long long x)
{
int y=k;
long long gg=(b-1)*a-b-x;
while(gg>=0)
{
y-=gg/b+1;
if(y<=0)
return 1;
gg-=a;
}
return 0;
}
int main()
{
long long l,r,mid;
scanf("%lld%lld%lld",&a,&b,&k);
if(a<b)
{
a^=b;
b^=a;
a^=b;
}
l=1,r=a*b;
while(l!=r)
{
mid=(l+r+1)/2;
if(ok(mid))
l=mid;
else
r=mid-1;
}
printf("%lld\n",l);
return 0;
} 
投递中国一汽等公司10个岗位 >
阿里云二面51人在聊