轻拍牛头的两种写法

利用前数筛选后数，类似欧拉筛的做法，最终得到每个数对应其他数约数的个数

方法一：

利用所给出的数对其倍数更新（出现问题 只过10个数据）

问题原因： 对于所给数据，如果存在很多较小数，筛选速度会从$O(n\{log}_2n)$退化成$O(n^2)$

python有退化问题版本

n = int(input())
N = 1000010
data = []
ans = [0]*(N)
for i in range(n):
    x = int(input())
    data.append(x)

for x in data:
    for j in range(x,N,x):  #又自己向所有数更新，得到所有数对应自己的约数个数
        ans[j] += 1

for x in data:
    print(ans[x] - 1)

方法二：

1. 首先利用cnt数组记录所有给出数字的数量

2. i先从1开始逐步完成更新（作为约束），使对应的倍数得到该数i的数量

3. 输出每个数对应约数

python版本

n = int(input())

N = 1000010
cnt = [0]*(N)
ans = [0]*(N)

data = []
for i in range(n):
    x = int(input())
    data.append(x)
    cnt[x] += 1

for i in range(1,N):
    for j in range(i,N,i):
        ans[j] += cnt[i]

for x in data:
    print(ans[x] - 1)