有道题目一时半会解不出来,简单我感觉应该是挺简单的,但是想不出来怎么解,考试结束后也没想到很好的方案。请教下
给定一个整数范围,范围内数字依次递增,步长为 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 的数组,一个个从里面剔除掉,然后算剩余多少元素
1
KKKKKK 2019-04-27 00:11:18 +08:00 via iPhone
最简单的,直接想到的 O(nm) 算法
|
2
dfjslkjdf 2019-04-27 00:18:04 +08:00 1
比如,1-100,
剔除 2,5,7 倍数; 可以每 2*5*7 为一个数组。 |
3
LxExExl 2019-04-27 00:26:09 +08:00 via iPhone
剔除一个数 (b-a)/x 即可 注意处理边界
剔除多个数先把倍数去掉然后就和去掉一个数一样了吧 |
4
Vegetable 2019-04-27 00:30:09 +08:00
2# 的思路我觉得不错.取 n 个数的最小公倍数 a.求出 0~a 之间有多少个,后边就不需要遍历了,简单处理一下就行了
|
5
shs10978 2019-04-27 00:32:44 +08:00 via Android
划掉数字互质的话 dp 应该能做吧,O(sqrt(n)*m)。不互质会复杂一些。
|
6
JCZ2MkKb5S8ZX9pq 2019-04-27 00:33:17 +08:00
假设范围 r1-r2,要剔除的基数[n1,n2,n3,...]
第一步找出某一个基数在范围里有几个吧,比如 c1。 如果是 python 语法 c1 = r2//n1-r1//n1 第二步穷举一下公约数,计算出现次数再扣掉。 不过如果基数的个数也很多的话,复杂度还是很高啊。 |
7
hakono OP @LxExExl 其实我最开始就是这样做的。
但后来发现,给定数字还得考虑公倍数。比如要去除 31 46 的倍数的话,还得考虑 31 46 的公倍数 1426 多减去的情况。然后如果给定的数字数量比较多给了 10 几个的话,每个数字互相之间的公倍数都得考虑 |
8
shs10978 2019-04-27 00:35:15 +08:00 via Android
嗯有点想复杂了,如果划掉的 m 个数字最小公倍数远远小于 n 的话,2 楼方法更好一些
|
9
hakono OP @JCZ2MkKb5S8ZX9pq 是的,我一开始就是这么想着去解的,但是给定的数字数量不少,10 到 30 个之间,还得穷举每种组合的公倍数。然后穷举出来的公倍数还得推算下公倍数,多次重复的情况也得剔除。
最后写出来结果是有挺多题答案是错的。所以才觉得这个方法可能有点问题或者哪里没有考虑清楚 |
10
maggch 2019-04-27 00:47:51 +08:00
容斥
|
11
starrycat 2019-04-27 00:51:43 +08:00 via Android
想到了素数筛选法,有点类似😂
|
12
Vegetable 2019-04-27 00:54:10 +08:00
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 没格式的话忍一忍...我测试没什么问题. |
13
Vegetable 2019-04-27 00:56:10 +08:00 1
|
15
hakono OP @Vegetable 感谢代码!不过在给定范围很大的情况下,代码执行时间会极长。因为 for range(1,r),所以在比如
r = 1000000000000000000 x = ['29516', '34882', '63315', '28983', '7176', '96533', '33422', '84834', '43803', '61310'] 的时候,执行时间很久 |
18
liyunlong41 2019-04-27 01:34:51 +08:00 via iPhone 1
这题感觉是典型的容斥啊。
假设给定四个数 和总数 n。 容斥原理计算四个数的倍数在 n 范围内的数量 m=sum(n/单个数)-sum(n/任意两数公倍数+sum(n/任意三数公倍数)-sum(n/四个数的公倍数) 最终结果就是 n-m |
19
clatisus 2019-04-27 01:36:54 +08:00 via iPhone
如果剔除的数字个数很少的话,可以枚举它们的子集,然后用容斥原理。
假设剔除 m 个数字,复杂度就 O(2^m)。 |
20
clatisus 2019-04-27 01:38:24 +08:00 via iPhone
@clatisus 补充:这样 n 不管多大都可以,如果是区间 [l, r] 的话,就 r 的答案减去 l - 1 的答案。
|
23
liyunlong41 2019-04-27 02:55:41 +08:00
花时间用 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) } ` |
24
liyunlong41 2019-04-27 02:58:40 +08:00
@liyunlong41 代码格式乱了,不太会搞,贴在网页上吧: https://github.com/hackssssss/test_git/blob/master/rc.go
|
25
geelaw 2019-04-27 04:43:38 +08:00
要删除的数字数目不多的时候可以用容斥原理,枚举子集进行公倍数的删除和加回即可。
这样需要的时间是 O(poly(log n) * 2^m poly(m)),其中 n 是范围,m 是要删除的数的个数。 并不知道是否有多项式时间算法( |
26
mooncakejs 2019-04-27 16:27:21 +08:00
约瑟夫环问题
|