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

[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 的数组，一个个从里面剔除掉，然后算剩余多少元素

[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]

约瑟夫环问题