[1,1e18] 中不能被 [2,10] 中的任何整数整除的正整数个数
Number of positive integers in [1,1e18] that cannot be divided by any integers in [2,10]
我在尝试解决以下问题时遇到困难：
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)。但这对这个问题不起作用（我不明白那个解决方案）。
有人可以告诉我如何解决这个问题吗？
这是处理此问题的方法。
首先要考虑如何将其拆分成多个部分。对于这样的问题，从最小公分母 (LCD) 开始——在本例中为 2,520（可被所有小于 10 的数字整除的最小数字）。
想法是如果 x 不能被 2-10 中的任何数整除，那么 x + 2,520 也不能被整除。
因此，您可以将问题分为两部分：
- 1 到 2,520 之间的数字 "relatively prime" 与 2-10 之间的数字有多少？
- 2,520 进入您的目标数多少次？您还需要考虑余数。
[2,10] 中唯一的物质数是那些 2, 3, 5, 7
的质数
所以，比方说，[2,10]中的数不能被整数整除就是这个数不能被{2,3,5,7}
整除
也等于[1,n]之间的总数减去除以{2,3,5,7}.
的任意组合的所有数字
所以，这是有趣的部分：从 [1,n] 中除以 2 的数字是多少？
答案是n/2（为什么？很简单，因为每2个数，就有1个数除以2）
同理，5除以多少个数？答案是n/5
...
那么，我们找到答案了吗？不，因为我们发现我们已经将那些除以 {2, 5} 或 {2, 7} ... 的数字加倍计数，所以现在，我们需要减去它们。
但是等等，似乎我们减去除以 {2,5,7} 的那些...所以我们需要将其加回去
...
继续这样做，直到处理完所有组合，
所以应该是2^4的组合，一共是16个，处理起来比较小
看看 Inclusion-Exclusion principle 以获得更好的理解。
祝你好运！
我在尝试解决以下问题时遇到困难：
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)。但这对这个问题不起作用（我不明白那个解决方案）。
有人可以告诉我如何解决这个问题吗？
这是处理此问题的方法。
首先要考虑如何将其拆分成多个部分。对于这样的问题，从最小公分母 (LCD) 开始——在本例中为 2,520（可被所有小于 10 的数字整除的最小数字）。
想法是如果 x 不能被 2-10 中的任何数整除，那么 x + 2,520 也不能被整除。
因此，您可以将问题分为两部分：
- 1 到 2,520 之间的数字 "relatively prime" 与 2-10 之间的数字有多少？
- 2,520 进入您的目标数多少次？您还需要考虑余数。
[2,10] 中唯一的物质数是那些 2, 3, 5, 7
所以，比方说，[2,10]中的数不能被整数整除就是这个数不能被{2,3,5,7}
也等于[1,n]之间的总数减去除以{2,3,5,7}.
所以，这是有趣的部分：从 [1,n] 中除以 2 的数字是多少？
答案是n/2（为什么？很简单，因为每2个数，就有1个数除以2）
同理，5除以多少个数？答案是n/5
...
那么，我们找到答案了吗？不，因为我们发现我们已经将那些除以 {2, 5} 或 {2, 7} ... 的数字加倍计数，所以现在，我们需要减去它们。
但是等等，似乎我们减去除以 {2,5,7} 的那些...所以我们需要将其加回去
...
继续这样做，直到处理完所有组合， 所以应该是2^4的组合，一共是16个，处理起来比较小
看看 Inclusion-Exclusion principle 以获得更好的理解。
祝你好运！