请教一道某公司的（简单？）算法题？

[hakono]

有道题目一时半会解不出来，简单我感觉应该是挺简单的，但是想不出来怎么解，考试结束后也没想到很好的方案。请教下

给定一个整数范围，范围内数字依次递增，步长为 1 如: 1 ~ 10

然后再给定几个数字，将这些数的倍数从给定的整数范围内剔除，问整数范围内还剩下几个数字

说起来抽象，举个例子就是：

出题者给定个整数范围比如1~10, 有十个数字

然后出题者给出几个要剔除的数字如：2 4 5，因为 2 的倍数是 2 4 6 8 , 4 的倍数是 4 8，5 是 5 10 从1~10中剔除这几个数，剩下1 3 7 9 剩余数量为 4

这个问题比较困难的地方在于，实际做题时，给出的数字范围是极大的比如 1~999999999999999999

500000000~100000000000000000000

这种

不可能简单搞个长度为 n 的数组，一个个从里面剔除掉，然后算剩余多少元素

[KKKKKK]

最简单的，直接想到的 O(nm) 算法

[dfjslkjdf]

比如，1-100，
剔除 2，5，7 倍数；
可以每 2*5*7 为一个数组。

[LxExExl]

剔除一个数 (b-a)/x 即可 注意处理边界
剔除多个数先把倍数去掉然后就和去掉一个数一样了吧

[Vegetable]

2# 的思路我觉得不错.取 n 个数的最小公倍数 a.求出 0~a 之间有多少个,后边就不需要遍历了,简单处理一下就行了

[shs10978]

划掉数字互质的话 dp 应该能做吧，O(sqrt(n)*m)。不互质会复杂一些。

[JCZ2MkKb5S8ZX9pq]

假设范围 r1-r2，要剔除的基数[n1,n2,n3,...]

第一步找出某一个基数在范围里有几个吧，比如 c1。
如果是 python 语法 c1 = r2//n1-r1//n1

第二步穷举一下公约数，计算出现次数再扣掉。
不过如果基数的个数也很多的话，复杂度还是很高啊。

[hakono]

@LxExExl 其实我最开始就是这样做的。

但后来发现，给定数字还得考虑公倍数。比如要去除 31 46 的倍数的话，还得考虑 31 46 的公倍数 1426 多减去的情况。然后如果给定的数字数量比较多给了 10 几个的话，每个数字互相之间的公倍数都得考虑

[shs10978]

嗯有点想复杂了，如果划掉的 m 个数字最小公倍数远远小于 n 的话，2 楼方法更好一些

[hakono]

@JCZ2MkKb5S8ZX9pq 是的，我一开始就是这么想着去解的，但是给定的数字数量不少，10 到 30 个之间，还得穷举每种组合的公倍数。然后穷举出来的公倍数还得推算下公倍数，多次重复的情况也得剔除。
最后写出来结果是有挺多题答案是错的。所以才觉得这个方法可能有点问题或者哪里没有考虑清楚

[maggch]

容斥

[starrycat]

想到了素数筛选法，有点类似😂

[Vegetable]

from functools import reduce


def rm(x, r):
_min = reduce(lambda x, y: x*y, x)
circulate, rest = divmod(r, _min)
r = common = 0
for i in range(1, _min):
for j in x:
if i % j == 0:
break
else:
common += 1
if i <= rest:
r += 1
return common*circulate+r


if __name__ == "__main__":
x = [2, 5, 7]
r = 10000
a = rm(x, r)
c = 0
for i in range(1, r):
for j in x:
if i % j == 0:
break
else:
c += 1
print(a)
assert c == a

没格式的话忍一忍...我测试没什么问题.

[Vegetable]

https://gist.github.com/luliangce/04b759cc89aee74ed8d6e7cc2f097e74

[Vegetable]

..最小公倍数求错了
@Vegetable

[hakono]

@Vegetable 感谢代码！不过在给定范围很大的情况下，代码执行时间会极长。因为 for range(1,r)，所以在比如
r = 1000000000000000000
x = ['29516', '34882', '63315', '28983', '7176', '96533', '33422', '84834', '43803', '61310']
的时候，执行时间很久

[hakono]

@dfjslkjdf
@Vegetable
啊，这个 n 个数求公倍数思考了半天终于幡然醒悟！懂了 orz
果然人笨

[shs10978]

@hakono 15 楼这个例子答案是 999656713995364547 ？

[liyunlong41]

这题感觉是典型的容斥啊。
假设给定四个数 和总数 n。
容斥原理计算四个数的倍数在 n 范围内的数量 m=sum(n/单个数)-sum(n/任意两数公倍数+sum(n/任意三数公倍数)-sum(n/四个数的公倍数）
最终结果就是 n-m

[clatisus]

如果剔除的数字个数很少的话，可以枚举它们的子集，然后用容斥原理。

假设剔除 m 个数字，复杂度就 O(2^m)。

[clatisus]

@clatisus 补充：这样 n 不管多大都可以，如果是区间 [l, r] 的话，就 r 的答案减去 l - 1 的答案。

[hakono]

@shs10978 测试里的参考答案是 999656834379155073

[shs10978]

@hakono 那就对了。。我素数 list 范围取小了所以答案偏了一点。。dbq

[liyunlong41]

花时间用 golang 写了下程序，1e18 的样例已经能正确跑出结果，999656834379155073，用的是容斥原理，枚举数组所有子集，看子集个数，奇数个就减，偶数个就加。秒出结果，被乘法溢出搞了好久…… 代码凑活着看。
`
func gcd(x, y int64) int64 { //辗转相除法
tmp := x % y
if tmp > 0 {
return gcd(y, tmp)
}
return y
}
func lcm(x, y int64) int64 {
return x / gcd(x, y) * y //计算 lcm 的小技巧，先除 gcd，再乘另一个数，有效防止溢出
}
func main() {
var (
n = int64(1000000000000000000)
i = uint(1)
j = uint(0)
nums = []int{29516, 34882, 63315, 28983, 7176, 96533, 33422, 84834, 43803, 61310}
len = uint(len(nums))
)
sum := int64(0)
for i = 0; i < (1 << len); i++ {
count := 0
curLcm := int64(1)
ok := true
for j = 0; j < len; j++ {
if (i & (1 << j)) > 0 {
count++
tmp := curLcm
curLcm = lcm(int64(nums[j]), curLcm)
//这里判断乘法溢出！！被卡了好久
if curLcm > n || curLcm < tmp || curLcm % tmp != 0 || curLcm % int64(nums[j]) != 0 {
ok = false
break
}
}
}
if !ok {
continue
}
if count%2 == 1 {
sum -= n / curLcm
} else {
sum += n / curLcm
}
}
fmt.Println(sum)
}

`

[liyunlong41]

@liyunlong41 代码格式乱了，不太会搞，贴在网页上吧： https://github.com/hackssssss/test_git/blob/master/rc.go

[geelaw]

要删除的数字数目不多的时候可以用容斥原理，枚举子集进行公倍数的删除和加回即可。
这样需要的时间是 O(poly(log n) * 2^m poly(m))，其中 n 是范围，m 是要删除的数的个数。

并不知道是否有多项式时间算法（

[mooncakejs]

约瑟夫环问题