欧拉函数,POJ2407 Relatives——欧拉函数——Pku2407

此题是学习欧拉函数必做的模板题。
介绍一下欧拉函数：
设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; Var prime :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; begin if 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; begin fillchar(prime,sizeof(prime),1); prime[1]:=false; for i:=2 to maxn do if prime[i] then begin j:=i*2; while j0 do begin tot:=0;ans:=1; while (n<>1)and(tot1 then ans:=ans*(n-1); writeln(ans); readln(n); end; END.

Tags:  欧拉函数应用 什么是欧拉函数 欧拉函数

延伸阅读