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.