Divisors
原题：（权限限制没有超链接）
题目描述
给定m 个不同的正整数a1, a2……am，请对0 到m 每一个k 计算，在区间[1,n] 里有多少正整数是a 中恰好k 个数的约数。
输入输出格式
输入格式：
第一行包含两个正整数n;m，分别表示区间范围以及a 数组的大小。
第二行包含m 个不同的正整数a1,a2……am，表示a 数组。
输出格式：
输出m + 1 行，每行一个整数，其中第i 行输出k = i 的答案。
输入输出样例
输入样例#1：
10 3 4 6 7
输出样例#1：
4 4 1 1
输入样例#2：
5 1 8
输出样例#2：
2 3
说明
m<=200
n,ai<=10^9
个人解法：
（很久没有A题了）
虽然一看数据范围就知道从m入手。然而考场上没有一点思路，只想到枚举[1..n]的每一个数，暴力判断。
易知，事实上对于答案有影响的，不过是A[i]的约数罢了。
（只知道n^(1/4)分解质因数，却不知道n^(1/2)找因数，所谓智障）
我们枚举1到sqrt(A[i])的每一个数j，如果A[i] mod j=0，则找到了两个因数j与A[i] div j。
之后把这两个因数记录下来。
对于此题，我们需要做的就是将每一个A[i]的因数找出来，之后记录下来。我们最终需要的是这个因数作为了几个A[i]的因数。因此可以用Hash表实现（除了插入变为了地址冲突数的复杂度以外，没什么不好的）。
不过注意，一个完全平方数，枚举出来的sqrt(A[i])只需要插入一次。
代码如下：
type
inf=record
x,func,next:longint;//x为数字，func为出现次数
end;
var
Hash:array[0..100047] of longint;
E:array[0..600000] of inf;//Hash表
A,Ans:array[0..200] of longint;//Ans为答案，A为元素数组
n,m,i,j,k,sqrtw,top:longint;
function H(w:longint):longint;//Hash函数
begin
exit((w+(w shr 1 shl 1)) mod 100047);
end;
procedure Find(x:longint);//查询，如果存在，则将出现次数+1，否则插入这个数
var
v,u:longint;
begin
v:=H(x);
u:=Hash[v];
while u<>0 do
begin
if E[u].x=x then
begin
inc(E[u].func);
exit;
end;
u:=E[u].next;
end;
inc(top);
E[top].x:=x;
E[top].func:=1;
E[top].next:=Hash[v];
Hash[v]:=top;
end;
begin
read(n,m);//读入
for i:=1 to m do
read(A[i]);
for i:=1 to m do//枚举元素
begin
sqrtw:=trunc(sqrt(A[i]));
for j:=1 to sqrtw do
if A[i] mod j=0 then
begin
k:=A[i] div j;
if j<=n then Find(j);
if k<>j then
if k<=n then Find(k);
end;
end;
for i:=1 to top do
inc(Ans[E[i].func]);//计算答案
writeln(n-top);//输出
for i:=1 to m do
writeln(Ans[i]);
end.