输入N,输出phi(N)
这样的单个值欧拉函数程序一般见于部分数论题,以及有时候求逆元且取模的数不是质数的情况(逆元:A/B=A*Bphi(p)-1 (mod p),一般常见题中p是质数,phi(p)-1=p-2)
(Tip:我是来水经验的不解释,不过话说真的好久没写这个了TT)
1 var i:int64;
2 function Eula(x:int64):int64;
3 var res:int64;i:longint;
4 begin
5 res:=x;
6 for i:=2 to trunc(sqrt(x)) do
7 begin
8 if (x mod i)=0 then
9 begin
10 res:=(res div i)*(i-1);
11 while (x mod i)=0 do x:=x div i;
12 end;
13 end;
14 if x>1 then res:=(res div x)*(x-1);
15 exit(res);
16 end;
17 begin
18 readln(i);writeln(Eula(i));
19 readln;
20 end.