[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 以获得更好的理解。
祝你好运!