找出给定N个数中K的倍数

Question

You are given N numbers. Now you have Q queries. For each query you will be given an integer K

Input Format The first line consists of number N. Next N line contains N numbers. Next line contains number of queries Q. Next Q lines contains Integer K for each query

Output Format Output Q lines the answer for every query.

Constraints 1 <= N <= 10^5; 1 <= numbers <= 10^5; 1 <= Q <= 10^5; 1 <= K <= 10^5

Sample Input

4
5
8
10
8
1
2

Sample Output

3

我的代码，得到一个使用78000个输入的失败测试用例：

ans = [] 
def countSieve(arr, n): 
    MAX=max(arr) 
    global ans 
    ans = [0]*(MAX + 1) 
    cnt = [0]*(MAX + 1) 
    for i in range(n): 
        cnt[arr[i]] += 1
    for i in range(1, MAX+1): 
        for j in range(i, MAX+1, i): 
            ans[i] += cnt[j] 

def countMultiples(k): 
    return(ans[k]) 

n=int(input())
a=[]
count=0
for i in range(n):
    j=int(input())
    a.append(j)
countSieve(a,n)
q=int(input())
k=[]
for i in range(q):
    c=int(input())
    k.append(c)
i=0
for i in k:
    print(countMultiples(i))

Answer 1

问题是您创建了一个大小为MAX(a)的数组，其中a是您的n编号列表。例如，如果MAX(a) = 10^5，这是低效的

您应该找到另一种方法来检查数字a是否是数字B的倍数，例如A%B == 0（使用模）

尝试删除countSieve并更改countMultiples

def countMultiples(query, numbers):
    count = 0
    for i in numbers:
        if i%query == 0:
            count += 1
    return count

n=int(input())
numbers = []
for i in range(n):
    j=int(input())
    numbers.append(j)
q=int(input())
queries = []
for i in range(q):
    c=int(input())
    queries.append(c)
for i in queries:
    print(countMultiples(i, numbers))

编辑：

这里有一个优化。首先我搜索数字除数，对于每个除数，我在dictd中增加一个计数器，然后对于查询qI printd[q]，这是n个数字中存在的倍数的确切数量

搜索数n的除数的方法是：我做一个循环，直到n的平方根，然后对于每个除数i，我还加上r = n//i

我还使用dict divs来存储每个数字n的除数，以便在我已经找到它们时不会重新计算它们

试试这个（它成功地解决了问题https://hack.codingblocks.com/app/dcb/938）：

import math
d = {}
divs = {}

for _ in range(int(input())):
    num = int(input())
    if num in divs:
        for e in divs[num]:
            d[e] = d.get(e, 0) + 1
    else:
        div_list = []
        for i in range(1, math.floor(math.sqrt(num)) + 1):
            if not num % i:
                div_list.append(i)
                d[i] = d.get(i, 0) + 1
            r = num // i
            if (not num % r and r != i):
                div_list.append(r)
                d[r] = d.get(r, 0) + 1
        divs[num] = div_list

for i in range(int(input())):
    q = int(input())
    print(d.get(q, 0))

Answer 2

或者，您可以尝试计算每个数字出现的频率，然后检查k的每个倍数的计数，直到N个数字中的最大值

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)

乍一看，这与其他方法没有太大区别，我认为理论上这甚至还有O（N*Q），但对于Q的大值，这应该会有很大的提升

假设Q=100000。对于所有K>；10（即除K的10个值外的所有值）您最多只需检查10000个倍数（因为m <= 100,000）。对于所有K>；10000（即90%的可能值）您只需检查最多10个倍数，对于50%的Ks，只需检查K本身

换句话说，除非我的逻辑有错误，在N=Q=100000的最坏情况下，你只有110万张支票，而不是1000000000

>>> N = Q = 100000
>>> sum(N//k for k in range(1,Q+1))
1166750

（这假设所有K都不同，但如果不是，则可以将结果缓存在dict中，然后也只需要对重复项进行一次检查。）

---

仔细观察，这种方法实际上非常类似于您的筛子所做的，只是更加紧凑，根据需要计算每个k的值，而不是一次计算所有值

---

我使用gen_input(n, q, max_k)的随机输入做了一些时序分析。首先，所有算法似乎产生相同的结果。对于较小的输入大小，在速度上没有显著差异（除了朴素的模），并且您的原始筛确实是最快的。对于较大的输入（最大值），您的输入仍然是最快的（甚至是更大的幅度），而divisors方法的速度要慢得多

>>> 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

不知道为什么在@phoenixo的divisors据称有效时，你和我的算法会超时（不过没有尝试过）