SGU 117 — Counting
给出n个数,判断它们的m次方能不能被k整除.
对每个数和k分解质因数即可(注意对于每个数只需要分解k的因子).
{
SGU 117; Counting
- sqybi’s code
}
//for my winsty
program sgu117_sqybi;
const
nn = 10000;
var
i, j, k, kk, l, n, m, s, t: longint;
a, b, p: array[1..nn]of longint;
f: boolean;
begin
readln(n, m, k);
kk := k;
l := 0;
for i:=2 to kk do begin
if k = 1 then break;
if k mod i = 0 then begin
inc(l);
p[l] := i;
while k mod i = 0 do begin
inc(a[l]);
k := k div i;
end;
end;
end;
s := 0;
for i:=1 to n do begin
read(t);
fillchar(b, sizeof(b), 0);
f := true;
for j:=1 to l do begin
while t mod p[j] = 0 do begin
inc(b[j]);
t := t div p[j];
end;
b[j] := b[j] * m;
if b[j] < a[j] then begin
f := false;
break;
end;
end;
if f then inc(s);
end;
writeln(s);
end.
阅读(119 次)