歐拉函數的定義:E(k)=([1,n-1]中與n互質的整數個數).
因為任意正整數都可以唯一表示成如下形式:
k=p1^a1*p2^a2*……*pi^ai;(即分解質因數形式)
可以推出:E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1))
=k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi);
=k*(1-1/p1)*(1-1/p2)....(1-1/pk)
ps：在程序中利用歐拉函數如下性質，可以快速求出歐拉函數的值(a為N的質因素)
若(N%a==0 && (N/a)%a==0) 則有:E(N)=E(N/a)*a;
若(N%a==0 && (N/a)%a!=0) 則有:E(N)=E(N/a)*(a-1);
推薦題目：
入門：
poj3090 Visible Lattice Points
poj2407 Relatives
poj2478 Farey Sequence
歐拉函數高級應用：
poj2480 Longge's problem
poj1091 跳蚤
posted on 2007-10-28 17:51
R2 閱讀(765)
評論(0) 編輯 收藏 引用