SGU 102 — Coprimes
求1到n中与n互素的数的个数.标准做法是欧拉函数,这道题范围小,随便就可以搞掉.
欧拉函数varphi(n)的求法:
假设n的质因数分解为:n=p1^a1+p2^a2+…+pk^ak,其中p1到pk是互不相等的k个素数,那么
varphi(n)=n*((p1-1)/p1)*((p2-1)/p2)*…*((pk-1)/pk)
然后随便一写就好…
{
SGU 102; Coprimes
- sqybi’s code
- 欧拉函数
}
//for my winsty
program sgu102_sqybi;
var
n, m, nt, i: longint;
a: array[1..10000]of longint;
begin
readln(n);
nt := n;
m := 0;
for i:=2 to n do begin
if n = 1 then break;
if n mod i = 0 then begin
inc(m);
a[m] := i;
while n mod i = 0 do n := n div i;
end;
end;
for i:=1 to m do
nt := nt * (a[i] - 1) div a[i];
writeln(nt);
end.
阅读(104 次)