此题是学习欧拉函数必做的模板题。
介绍一下欧拉函数：
设n为正整数，欧拉函数φ(n)定义为不超过n且与n互质的正整数的个数。
三个引理：
1、对于某一素数p，则φ(p)=p-1
2、对于某一素数p的幂次p^a,φ(p^a)=(p-1)*p^(a-1)
3、对于某一合数n可分解为两个素数之积a*b，则φ(n)=φ(a)*φ(b)
证明：
1、显然
2、对于p^a-1个比p^a小的数，其中所有p的倍数可以表示为t*p{t=1,2,3,…,p^(a-1)-1}，所以φ(p^a)=p^a-1(-p^(a-1)-1)=(p-1)*p^(a-1)
3、在比a*b小的a*b-1个整数中，只有那些既与a互质、又与b互质的数才会满足与a*b互质，而显然满足条件的有φ(a)*φ(b)个数，所以φ(a*b)=φ(a)*(b)
扩展引理：
(p1^a1)*(p2^a2)*(p3^a3)*…*(pk^ak)为正整数n的素数幂表示形式，那么有φ（n）=φ(p1^a1)*φ(p2^a2)*φ(p3^a3)*…*φ(pk^ak)
欧拉定理：
若a与m互质，则a^(φ(m))在以m为模的情况下与１同余。
本题代码实现：
Program Relatives;//By_Thispoet
Const maxn=100000;
Varprime :Array[1..maxn]of Boolean;list :Array[0..maxn]of Longint;i,j,k,n,ans,tot :Longint;Function Power(i,j:Longint):Longint;
var temp:Longint;
beginif j=0 then exit(1);temp:=Power(i,j>>1);temp:=temp*temp;if odd(j) then temp:=temp*i;exit(temp);end;Procedure Prime_Prepare;
beginfillchar(prime,sizeof(prime),1);prime[1]:=false;for i:=2 to maxn do if prime[i] then beginj:=i*2;while j<maxn do beginprime[j]:=false;inc(j,i);end;end;for i:=2 to maxn do beginif prime[i] then begininc(list[0]);list[list[0]]:=i;end;end;end;BEGINreadln(n);Prime_Prepare;while n<>0 dobegintot:=0;ans:=1;while (n<>1)and(tot<list[0]) do begininc(tot);if n mod list[tot]=0 then begink:=0;while n mod list[tot]=0 do begininc(k);n:=n div list[tot];end;ans:=ans*(list[tot]-1)*Power(list[tot],k-1);end;end;if n<>1 then ans:=ans*(n-1);writeln(ans);readln(n);end;END.