m**********e
发帖数: 52 | 1 求1,000,000内不能被array中的任意数整除的数总共有多少个，比如array = [2,4,9,
10]， 肯定不能用暴力，应该是减减加加 | Y**G
发帖数: 1089 | 2 用筛法就可以了吧。比如那个例子，先把2的倍数全部去掉，然后在去掉4的倍数（这步
可以优化，因为4的倍数必然是2的倍数），然后在去掉9的倍数，10的倍数（也可以优
化），剩下的就是要的了吧。 | m**********e
发帖数: 52 | 3 应该是用Inclusion–exclusion principle，这里的array size 很小，但总数很大
【在 Y**G 的大作中提到】
: 用筛法就可以了吧。比如那个例子，先把2的倍数全部去掉，然后在去掉4的倍数（这步
: 可以优化，因为4的倍数必然是2的倍数），然后在去掉9的倍数，10的倍数（也可以优
: 化），剩下的就是要的了吧。
| P******r
发帖数: 1342 | | Y**G
发帖数: 1089 | 5 还有一个办法
第一步，先把数组优化，冗余的去掉，如果数组是[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
发帖数: 186 | 6 这样行不?
将数组排序为 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个数
|
|
