首先有一个结论:凑不出来的数形如 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; }
全部评论
(1) 回帖