欧拉函数
欧拉函数phi(i)表示1到i-1中与i互质的数的个数。
线性筛求欧拉函数
筛法显然是适用于一些很大范围内的求解。
详情转链接
接下来，我们就可以利用欧拉函数解决一些有趣的问题了。一般要用到欧拉函数的地方都是大范围使用，所以这不失为一种好的方法。
通式求欧拉函数
这个就是利用了欧拉函数的通式来求解。
phi(x)=x*(1-1/p1)*(1-1/p2)*……*(1-1/pi)
pi为x的质因数（每一个质因数只会乘一遍）。
所以我们就先质因数分解，之后再计算就可以了。
如果需要大数取模，就可能需要再写一个逆元。
代码如下：
type
inf=record
x:int64;
next:longint;
end;
var
x,w:int64;
top:longint;
Hash:array[0..100047] of longint;
Fin:array[1..100000] of inf;//储存因子
//一下一大串都是pollard_rho质因数分解的过程，最后求欧拉函数的在phi函数中
function multiply(a,b,p:int64):int64;
begin
multiply:=0;
while b<>0 do
begin
if b and 1<>0 then multiply:=(multiply+a) mod p;
a:=a shl 1 mod p;
b:=b shr 1;
end;
end;
function power(a,b,p:int64):int64;
var
s,w:int64;
begin
s:=1;
w:=a;
while b<>0 do
begin
if b and 1<>0 then s:=multiply(s,w,p);
w:=multiply(w,w,p);
b:=b shr 1;
end;
exit(s);
end;
function Miller(x:int64):boolean;
var
vi,vk:longint;
vj,vl,u,t:int64;
begin
if x=1 then exit(false);
if x=2 then exit(true);
u:=x-1;
t:=0;
while u and 1=0 do
begin
u:=u shr 1;
inc(t);
end;
for vi:=1 to 8 do
begin
vj:=2+random(x-2);
vj:=power(vj,u,x);
for vk:=1 to t do
begin
vl:=multiply(vj,vj,x);
if vl=1 then
if (vj<>1) and (vj<>x-1) then exit(false);
vj:=vl;
end;
if vj<>1 then exit(false);
end;
exit(true);
end;
function H(x:int64):longint;
begin
exit((x shl 1) mod 100047);
end;
procedure ins(x:int64);
var
v,u:longint;
begin
v:=H(x);
u:=Hash[v];
while u<>0 do
begin
if Fin[u].x=x then exit;
u:=Fin[u].next;
end;
inc(top);
Fin[top].x:=x;
Fin[top].next:=Hash[v];
Hash[v]:=top;
end;
function gcd(a,b:int64):int64;
var
c:int64;
begin
c:=a mod b;
while c<>0 do
begin
a:=b;
b:=c;
c:=a mod b;
end;
exit(b);
end;
function pollard(n,c:int64):int64;
var
x,y,d,s,t:int64;
begin
s:=1;
t:=2;
x:=1+random(n-2);
y:=x;
while true do
begin
x:=(multiply(x,x,n)+c) mod n;
d:=gcd(abs(x-y),n);
if (d<>1) and (d<>n) then exit(d);
if x=y then exit(n);
inc(s);
if s=t then
begin
t:=t shl 1;
y:=x;
end;
end;
end;
procedure decompose(x:int64);
var
y:int64;
begin
if Miller(x) then
begin
ins(x);
exit;
end;
y:=x;
while y>=x do
y:=pollard(x,2+random(x-2));
decompose(y);
decompose(x div y);
end;
function phi(x:int64):int64;//计算欧拉函数
var
vi:longint;
begin
for vi:=1 to top do
x:=x div Fin[vi].x*(Fin[vi].x-1);
exit(x);
end;
begin
read(x);//读入
randomize;
decompose(x);//质因数分解
w:=phi(x);//计算欧拉函数
writeln(w);//输出
end.
然而pollard_rho让我写的很悲哀——真正的重点phi才那么一点点……