m*e
2 楼
求1,000,000内不能被array中的任意数整除的数总共有多少个，比如array = [2,4,9,
10]， 肯定不能用暴力，应该是减减加加
10]， 肯定不能用暴力，应该是减减加加
L*x
3 楼
太次了,决定出门.
Y*G
4 楼
用筛法就可以了吧。比如那个例子，先把2的倍数全部去掉，然后在去掉4的倍数（这步
可以优化，因为4的倍数必然是2的倍数），然后在去掉9的倍数，10的倍数（也可以优
化），剩下的就是要的了吧。
可以优化，因为4的倍数必然是2的倍数），然后在去掉9的倍数，10的倍数（也可以优
化），剩下的就是要的了吧。
m*e
5 楼
应该是用Inclusion–exclusion principle，这里的array size 很小，但总数很大
【在 Y**G 的大作中提到】
: 用筛法就可以了吧。比如那个例子，先把2的倍数全部去掉，然后在去掉4的倍数（这步
: 可以优化，因为4的倍数必然是2的倍数），然后在去掉9的倍数，10的倍数（也可以优
: 化），剩下的就是要的了吧。
【在 Y**G 的大作中提到】
: 用筛法就可以了吧。比如那个例子，先把2的倍数全部去掉，然后在去掉4的倍数（这步
: 可以优化，因为4的倍数必然是2的倍数），然后在去掉9的倍数，10的倍数（也可以优
: 化），剩下的就是要的了吧。
P*r
6 楼
小学奥赛题啊。。
Y*G
7 楼
还有一个办法
第一步，先把数组优化，冗余的去掉，如果数组是[2,4,9,10]
去冗余后，数组变成[2, 9]
第二步，求出最小公倍数
2和9的最小公倍数是18
把1000000分成很多段，每段有18个连续的数
[0, ...,17]
[18, ... 35]
...
最后一段是[999990, 999991, ... 999999]不满18个数
每段中，不能被2和9整除的数是18 - 18/2 - 18/9 + 1 = 8
最后一段，有10个数，不能被2和9整除的有: 10 - 10/2 - 10/9 - 10 / (2*9) = 10 -
5 - 1 - 0 = 4
所以总共有8 * (1000000/18) + 4 = 444444个数介于0和1000000(包括0， 不包括
1000000)不能被2, 4, 9, 10整除。
【在 Y**G 的大作中提到】
: 用筛法就可以了吧。比如那个例子，先把2的倍数全部去掉，然后在去掉4的倍数（这步
: 可以优化，因为4的倍数必然是2的倍数），然后在去掉9的倍数，10的倍数（也可以优
: 化），剩下的就是要的了吧。
第一步，先把数组优化，冗余的去掉，如果数组是[2,4,9,10]
去冗余后，数组变成[2, 9]
第二步，求出最小公倍数
2和9的最小公倍数是18
把1000000分成很多段，每段有18个连续的数
[0, ...,17]
[18, ... 35]
...
最后一段是[999990, 999991, ... 999999]不满18个数
每段中，不能被2和9整除的数是18 - 18/2 - 18/9 + 1 = 8
最后一段，有10个数，不能被2和9整除的有: 10 - 10/2 - 10/9 - 10 / (2*9) = 10 -
5 - 1 - 0 = 4
所以总共有8 * (1000000/18) + 4 = 444444个数介于0和1000000(包括0， 不包括
1000000)不能被2, 4, 9, 10整除。
【在 Y**G 的大作中提到】
: 用筛法就可以了吧。比如那个例子，先把2的倍数全部去掉，然后在去掉4的倍数（这步
: 可以优化，因为4的倍数必然是2的倍数），然后在去掉9的倍数，10的倍数（也可以优
: 化），剩下的就是要的了吧。
r*g
8 楼
这样行不?
将数组排序为 a[0] <= a[1] <= ... <= a[K]
然后对第k步, 得到count[k], 这里count[k]是对于
1~N个数当中无法被a[0]~a[k]整除的数的个数
然后第k+1步: 需要扣掉count[k]中能被a[k+1]整除的数
的个数:
1. 如果a[k+1]是a[i](0<=i<=k)的倍数:不需要扣除:
因为不能被a[i]整除就一定不能被a[k+1]整除.
2. a[k+1]不是任何之前的数的倍数:
则变为寻找:
"能被a[k+1]整除的数, 但不能被a[0~k]整除"
这相当于寻找 1~N/a[k+1]中无法被a[0~k]整除的元素的个数
(也许可以利用count[k]来得到这个值, 而不用再算一次, 因为
这些元素分布是均匀的, 估计可以简单的乘除得到)
【在 Y**G 的大作中提到】
: 还有一个办法
: 第一步，先把数组优化，冗余的去掉，如果数组是[2,4,9,10]
: 去冗余后，数组变成[2, 9]
: 第二步，求出最小公倍数
: 2和9的最小公倍数是18
: 把1000000分成很多段，每段有18个连续的数
: [0, ...,17]
: [18, ... 35]
: ...
: 最后一段是[999990, 999991, ... 999999]不满18个数
将数组排序为 a[0] <= a[1] <= ... <= a[K]
然后对第k步, 得到count[k], 这里count[k]是对于
1~N个数当中无法被a[0]~a[k]整除的数的个数
然后第k+1步: 需要扣掉count[k]中能被a[k+1]整除的数
的个数:
1. 如果a[k+1]是a[i](0<=i<=k)的倍数:不需要扣除:
因为不能被a[i]整除就一定不能被a[k+1]整除.
2. a[k+1]不是任何之前的数的倍数:
则变为寻找:
"能被a[k+1]整除的数, 但不能被a[0~k]整除"
这相当于寻找 1~N/a[k+1]中无法被a[0~k]整除的元素的个数
(也许可以利用count[k]来得到这个值, 而不用再算一次, 因为
这些元素分布是均匀的, 估计可以简单的乘除得到)
【在 Y**G 的大作中提到】
: 还有一个办法
: 第一步，先把数组优化，冗余的去掉，如果数组是[2,4,9,10]
: 去冗余后，数组变成[2, 9]
: 第二步，求出最小公倍数
: 2和9的最小公倍数是18
: 把1000000分成很多段，每段有18个连续的数
: [0, ...,17]
: [18, ... 35]
: ...
: 最后一段是[999990, 999991, ... 999999]不满18个数
相关阅读
只有老板一个人的公司能申请H1B吗？之前效益不好。夏天面试要穿西服外套，打领带吗？谢谢。一道G老题紧急问题求助 H1b to F1, during process find another job and want to do H1b transfer请教问题如何在text file里找frequently occurring patterns?optvolunteer的简历需要非常正式吗在哪个能查公司办绿卡的政策？video clips about working for google问个linkedin题目求救(SOS)：OPT extension 杯具了，问一个filing的问题。 (转载)capital one的job fit assessment, 求建议和祝福国内保险公司精算岗招聘问opt期间保险问题Nike研发的待遇怎么样？Contractor 只干了几天就收到另一个Permanent job offer怎么办没有工作也可以申请EB2绿卡律师错了?求教: 什么是export compliance issues的政策?