<p>或者,您可以尝试计算每个数字出现的频率,然后检查<code>k</code>的每个倍数的计数,直到N个数字中的最大值</p>
<pre><code>import collections
n = int(input())
nums = [int(input()) for _ in range(n)]
counts = collections.Counter(nums)
m = max(nums)
q = int(input())
for _ in range(q):
k = int(input())
x = sum(counts[i] for i in range(k, m+1, k))
print(x)
</code></pre>
<p>乍一看,这与其他方法没有太大区别,我认为理论上这甚至还有O(N*Q),但对于Q的大值,这应该会有很大的提升</p>
<p>假设Q=100000。对于所有K>;10(即除K的10个值外的所有值)您最多只需检查10000个倍数(因为<code>m <= 100,000</code>)。对于所有K>;10000(即90%的可能值)您只需检查最多10个倍数,对于50%的Ks,只需检查K本身</p>
<p>换句话说,除非我的逻辑有错误,在N=Q=100000的最坏情况下,你只有110万张支票,而不是1000000000</p>
<pre><code>>>> N = Q = 100000
>>> sum(N//k for k in range(1,Q+1))
1166750
</code></pre>
<p>(这假设所有K都不同,但如果不是,则可以将结果缓存在dict中,然后也只需要对重复项进行一次检查。)</p>
<hr/>
<p>仔细观察,这种方法实际上非常类似于您的筛子所做的,只是更加紧凑,根据需要计算每个<code>k</code>的值,而不是一次计算所有值</p>
<hr/>
<p>我使用<code>gen_input(n, q, max_k)</code>的随机输入做了一些时序分析。首先,所有算法似乎产生相同的结果。对于较小的输入大小,在速度上没有显著差异(除了朴素的模),并且您的原始筛确实是最快的。对于较大的输入(最大值),您的输入仍然是最快的(甚至是更大的幅度),而<code>divisors</code>方法的速度要慢得多</p>
<pre><code>>>> n, q = gen_input(10000, 1000, 1000)
>>> modulo(n, q) == mine(n, q) == sieve(n, q) == modulo(n, q)
True
>>> %timeit modulo(n, q)
1 loop, best of 3: 694 ms per loop
>>> %timeit mine(n, q)
10 loops, best of 3: 160 ms per loop
>>> %timeit sieve(n, q)
10 loops, best of 3: 112 ms per loop
>>> %timeit divisors(n, q)
1 loop, best of 3: 180 ms per loop
>>> n, q = gen_input(100000, 100000, 100000)
>>> %timeit mine(n, q)
1 loop, best of 3: 313 ms per loop
>>> %timeit sieve(n, q)
10 loops, best of 3: 131 ms per loop
>>> %timeit divisors(n, q)
1 loop, best of 3: 1.36 s per loop
</code></pre>
<p>不知道为什么在@phoenixo的<code>divisors</code>据称有效时,你和我的算法会超时(不过没有尝试过)</p>