algorithm - [1,1e18] 中不能被 [2,10] 中的任何整数整除的正整数个数

Question

我在尝试解决以下问题时遇到困难:

For Q queries, Q <= 1e6, where each query is a positive integer N, N <= 1e18, find the number of integers in [1,N] that cannot be divided by integers in [2,10] for each query.

我想过使用筛法为每个查询过滤掉 [1,1e18] 中的数字(类似于埃拉托色尼筛法)。但是，N 的值可能非常大。因此，我无法使用这种方法。我能做的最有用的观察是，以 0、2、4、5、6、8 结尾的数字是无效的。但这对我解决这个问题没有帮助。

我看到了类似 problem 的解决方案使用较少数量的查询(Q <= 200)。但它不适用于这个问题(我不明白那个解决方案)。

有人可以告诉我如何解决这个问题吗？

Answer 1

[2,10] 中唯一的质数是 2, 3, 5, 7

所以，比方说，[2,10] 中的数字不能被整数整除就是这个数字不能被{2,3,5,7}整除>

这也等于 [1,n] 之间的总数减去除以 {2,3,5,7} 的任意组合的所有数字.

那么，这是有趣的部分:[1,n] 有多少个数被 2 除？答案是n/2(为什么？很简单，因为每2个数，就有一个数除以2)

同样，5除以多少个数？答案是 n/5...

那么，我们找到答案了吗？不，因为我们发现我们将那些除以 {2, 5} 或 {2, 7} 的数字加倍计数...，所以现在，我们需要减去它们。

但是等等，好像我们是减去除以 {2,5,7} 的那些...所以我们需要把它加回来

...

继续这样做，直到处理完所有组合，所以应该有2^4的组合，一共16个，处理起来很小。

看看Inclusion-Exclusion principle以便更好地理解。

祝你好运!