mid 为什么要除以m
来源：8-7 复杂的二分查找（2）
慕仙3261604
2022-02-09
final int m = lcm(a, b);
long left = 1, right = ((long) n) *a;
while(left <= right){
final long mid = (left + right) >> 1;
if(mid/a + mid/b - mid/m >= n){//这里的mid除以m的意思？
right = mid -1;
}else{
left = mid + 1;
}
}
return (int)((right + 1)%1000000007);
写回答
1回答
-
javaman
2022-02-12
同学， 你好。
mid / x（下取整)表示从1到mid的所有数中有多少个是x的倍数。
那么mid / a + mid / b - mid / m求的是1到mid之间的数中有多少个数是a或者b的倍数。
这里m是a和b的最小公倍数。因为同时是a和b的倍数的数在mid / a 和mid / b中会各被计算一次，所以要把它减掉。
00
相似问题