竞赛讨论区 > E的非主流做法(
头像
图书馆工作人员
发布于 2021-05-21 23:24
+ 关注

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;
}


全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐