求助二分题目ID:9794

捕获
被这道二分题搞爆了,求大佬告诉我,这题与二分有什么关系?????

可以二分看看 mid 是第几个神奇数字,不难想到,若 x 是神奇数字,则是第几个是可以算出来的,具体的,我不知道
我不是到思路对不对,参考一下吧

我看一下数据范围,如果 n \le 10^7 那么就用一个set来存倍数,把 a\times 1,b\times1……a\times n,b\times n 放入set中,随后输出第K个元素

e,n<=10^9,a,b<=10^4

感谢各位大佬指点 :grinning_face: :grinning_face:(虽然好像还是搞不懂,可能本蒟蒻太菜了)

e,可能有点模糊,其实就是二分所有的数字,然后用数学得出它的编号是多少,若比预期小,则往后移,否则往前移

@Erin @栗子酱 这算不算 AC 代码?

把样例截图一下谢谢,WA代码发一下

对神奇数字进行二分,然后看这个mid前面有多少个神奇数字。单调性显然,所以可以二分。关键是怎么进行check。快速求出一个数之前有多少个满足条件的神奇数字。容斥算一下就好了应该。

先设两个初始值,x,y分别代表a和b,比较x和y,取出更小的数,将更小的放到x里(本质是默认x比y小),将x*2,将n-1,直到n等于1,输出x。可以尝试一下,希望有帮助。

in: 2 5 10
out: 16

AC代码?
@Erin

感谢大佬~~不过我看了一下,这段代码过不了样例 :face_with_tears_of_joy: :face_with_tears_of_joy:
附样例:in:1 2 3
out:2
又附:交上去WA 0分

WA代码是乱写的,就是看了就知道是骗分的那种······而且没有用二分,用的是O(1)算法
网页捕获_13-8-2025_13015_xinyoudui.com

?不是已经告诉你二分思路了吗还在骗分?

e,代码是发帖之前写的,为了回复12345

oo

那你过了吗?