如何找到解决任务的数学解决方案？

Question

我正在寻找旧编码竞赛的解决方案，我想知道他们是如何想出这个解决方案的。

问题是这样的：计算 numStart - numEnd 范围内有多少个唯一数字可被给定素数列表中的至少一个素数整除。

首先我认为 "Sure, let's just make a for loop that goes through the range of numStart - numEnd and check if I can divide my iterator with at least one of the primes"，这行得通，但它太慢了......那是我决定检查答案的时候。

我的代码：

# numStart: Start from number
# numEnd: End on number
# numOfPrimes: How many primes will we be checking

numStart,numEnd,numOfPrimes = map(int, input().split())
primes = list(map(int, input().split()))

# Input can look like this:
# >21 180 4
# >7 3 13 2

counter = 0
for testNum in range(numStart, numEnd + 1):
    for prime in primes:
        if testNum % prime == 0:
            counter += 1
            break

print(counter)
# Output would look like this:
# >118

解决方法：

from itertools import combinations

# numStart: Start from number
# numEnd: End on number
# numOfPrimes: How many primes will we be checking

numStart,numEnd,numOfPrimes = map(int, input().split())
primes = list(map(int, input().split()))

# Input can look like this:
# >21 180 4
# >7 3 13 2

result = 0
for j in range(1,numOfPrimes+1):
    for c in combinations(primes, j):
        num = 1
        for x in c: num *= x
        result += (-1)**(len(c)+1) * (numEnd//num - (numStart-1)//num)

print(result)
# Output would look like this:
# >118

我的问题真的是这个人是怎么想出来的？这是什么类型的数学，为什么它有效？

如果你至少能指引我正确的方向，我将非常感激！

Answer 1

这里是部分代码的简要总结。

给定的代码中有两个主要思想。第一个想法是，给定一个正整数num（不一定是质数），numStart到numEnd范围内被num整除的数的个数是

numEnd//num - (numStart-1)//num

这是因为从1到numStart能被num整除的数是(numStart-1)//num，从1到numEnd是numEnd//num。（我将让您了解这些公式如何正确处理这些范围的结束值。）

这是第二个想法。该公式适用于给定列表中的每个素数。但是问题要求计算该列表中可被 "by at least one prime" 整除的范围内的数字数。如果我们只是将每个质数的计数相加，我们将多次计算可被多个质数整除的数。处理这些多重计数的标准方法是 Inclusion–exclusion principle。如果您对这类问题感兴趣，您应该阅读那篇文章。代码行

for j in range(1,numOfPrimes+1):
    for c in combinations(primes, j):

使c成为素数列表的非空子集。我上面给你的公式是用来求子集中每个素数乘积的个数，乘以因子(-1)**(len(c)+1)做适当的inclusion/exclusion。然后添加所有这些产品。如果您不理解最后一部分，请阅读包含 - 排除文章。我应该补充一点，基本数论告诉我们，当且仅当素数的乘积除以该数时，不同素数的成员集全部除以该数——这就是 "prime" 限制出现问题的原因.

至于这个人是如何想出来的，计算机科学表明，没有确定的方法可以找出问题的算法。问题解决者只是利用他们的知识、经验、创造力和毅力坚持下去，直到问题得到解决。 George Polya 的 How to Solve It 一书是解决问题的经典之作。我强烈推荐这本书给你——它是平装本，而且很便宜。

如何找到解决任务的数学解决方案？

How to find a math solution for solving a task?

python

math

primes