歐拉函數(shù)的定義:
在數(shù)論中，對(duì)于正整數(shù)N,少于或等于N ([1,N]),且與N互質(zhì)的正整數(shù)(包括1)的個(gè)數(shù)，記作φ(n)。
φ函數(shù)的值：
φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) 其中p(1),p(2)…p(n)為x
的所有質(zhì)因數(shù);x是正整數(shù); φ(1)=1(唯一和1互質(zhì)的數(shù)，且小于等于1)砂轻。注意：每種質(zhì)因數(shù)只有一個(gè)。
例如:
φ(10)=10×(1-1/2)×(1-1/5)=4;
1 3 7 9
φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;
φ(49)=49×(1-1/7)=42;
歐拉函數(shù)的性質(zhì)：
(1) p^k型歐拉函數(shù):
若N是質(zhì)數(shù)p(即N=p),φ(n)= φ(p)=p(1-1/p)=p-1斤吐。 所以除了p自己本身外,[1,p-1]的任何數(shù)都與p互質(zhì),所以φ(p)=p-1,另外由公式得到φ(n)= φ(p)=p(1-1/p)=p-1搔涝。
若N是質(zhì)數(shù)p的k次冪(即N=p^k)， φ(n)= p^ k -p^(k-1) =(p-1)p^(k-1)和措。y因?yàn)槌藀的倍數(shù)以外,其他數(shù)都與N互質(zhì)庄呈。而是p的倍數(shù)的數(shù)有p,2p,3p...p^(k-1)*p,一共有p ^ ( k- 1)個(gè),所以有p^k -p ^ (k-1) =(p-1)p^(k-1)個(gè)數(shù)與p互質(zhì)。
(2)mn型歐拉函數(shù)
設(shè)m,n為正整數(shù),若m,n互質(zhì)派阱，φ(mn)=(m-1)(n-1)=φ(m)φ(n)诬留。容易知道m(xù)n與m的倍數(shù)或者n的倍數(shù)不互質(zhì),而n的倍數(shù)有n,2n,3n...mn,共有m個(gè),m的倍數(shù)有m,2m,3m...nm,共有n個(gè),又mn重復(fù)計(jì)數(shù),所以共有n+m-1個(gè),至于k1*n和k2*m中會(huì)不會(huì)有重復(fù)計(jì)數(shù)呢?因?yàn)閚,m為質(zhì)數(shù),要使得k1n=k2m,那么k1=n,k2=m;所以與mn互質(zhì)的有m*n-(n+m-1)=(m-1)*(n-1)=φ(m)φ(n)
(3)特殊性質(zhì):
若n為奇數(shù)時(shí)，φ(2n)=φ(n)贫母。
對(duì)于任何兩個(gè)互質(zhì) 的正整數(shù)a,n(n>2)有:a^φ(n)=1 mod n (恒等于)此公式即 歐拉定理
當(dāng)n=p 且 a與素?cái)?shù)p互質(zhì)(即:gcd(a,p)=1)則上式有: a^(p-1)=1 mod p (恒等于)此公式即 費(fèi)馬小定理
如果(a,c)互質(zhì)缩功，且c是素?cái)?shù)悼粮，則（a ^ b）%c=a ^ ( b % ( phi(c) ) )%c 惕它， phi(c) 是指c的歐拉函數(shù)
四 歐拉函數(shù)的延伸:
( 一 )
小于或等于n的數(shù)中褒墨，與n互質(zhì)的數(shù)的總和為：φ(n) * n / 2 (n>1)。
( 二 )
定義：n的原根x滿足條件0<x<n,并且有集合{ (xi mod n) | 1 <= i <=n-1 } 和集合{ 1, ..., n-1 }相等定理：如果p有原根橘原，則它恰有φ(φ(p))個(gè)不同的原根籍铁。
例題 a ^ b ^ c mod 1000000007
#include<stdio.h>
#include <string.h>
using namespace std;
#define Mod 1000000007
int powMod(int a,int b,int c)
{
int res=1,base=a;
while(b)
{
if(b&1) res=((long long)res*base)%c;
base=((long long)base*base)%c;
b>>=1;
}
return res;
}
int main()
{
int a,b,c;
while(~scanf("%d%d%d",&a,&b,&c))
{
int resul=powMod(b,c,Mod-1);
printf("%d\n",powMod(a,resul,Mod));
}
}
求歐拉函數(shù)的方法
( 一 ) 根據(jù)定義來實(shí)現(xiàn)
int euler(int n)
{
int m=sqrt(n+0.5);
int res=n;
for(int i=2;i<=m;i++)
{
if(n%i==0)
{
res=res/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) res=res/n*(n-1);
return res;
}
( 二 )篩選法打歐拉函數(shù)表
const int MAXN=1000010;
int phi[MAXN];
void phi_table(int n)
{
memset(phi,0,sizeof(phi));
phi[1]=1;
for(int i=1;i<=n;i++)
{
if(phi[i]==0)//i是質(zhì)數(shù)
{
for(int j=i;j<=n;j+=i)
{
if(phi[j]==0) phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}
}
}
