歐拉函數 乘法模逆元

今天來講一下歐拉函數及乘法模逆元
首先是歐拉函數
定義: 歐拉函數$φ(N)$是小于或等于$N$的正整數中與$N$互質的數的個數$(N>0)$
其值為
$φ(N)=N \times (1-1/P_1) \times (1-1/P_2) \times (1-1/P_3) \times ... \times (1-1/P_k)$
其中$P_i$為$N$的質因數，總共有$k個$

因此可以利用質數篩法在線性或趨近線性的時間內完成某一區間的歐拉函數:

	#define maxn 10000000
	int euler[maxn+5];
	bool is_prime[maxn+5];
	inline void init_euler(){
	is_prime[1]=1;//一不是質數
	for(int i=1;i<=maxn;i++)euler[i]=i;
	for(int i=2;i<=maxn;i++){
	if(!is_prime[i]){//是質數
	euler[i]--;
	for(int j=i<<1;j<=maxn;j+=i){
	is_prime[j]=1;
	euler[j]=euler[j]/i*(i-1);
	}
	}
	}
	}

view raw range phi.cpp hosted with ❤ by GitHub

計算單一數的歐拉函數值可利用平方根質數法求:

	inline int Euler(int n){
	int ans=n;
	for(int i=2;i*i<=n;i++){
	if(n%i==0){
	ans=ans/i*(i-1);
	while(n%i==0)n/=i;
	}
	}
	if(n>1)ans=ans/n*(n-1);
	return ans;
	}

view raw phi.cpp hosted with ❤ by GitHub

接下來介紹乘法模逆元
一整數$A$對同餘$B$之乘法模逆元是指滿足以下公式的整數$R$ $$A^{-1}≡R \; (mod \; B)$$
也可以寫成 $$AR≡1 \; (mod \; B)$$
根據歐拉定理: 當$gcd(A,B)=1$，$A^{φ(B)} ≡ 1 \; mod \;B$
(若$B$是質數，則$φ(B)=B-1$，競賽題目$B$大多為質數，不需求歐拉函數)
為了方便，我們定義 $X\%Y$ 表示$X$除以$Y$的餘數
顯然 $R=A^{φ(B)-1} \;\% \; B$ 是$A$的模$B$乘法模逆元，可以由次方快速冪再$\ord{logn}$的時間得到:

	inline long long pow_mod(int a,int b){//條件:gcd(a,b)=1
	long long mod=b,tmd=a,ans=1;
	for(b=Euler(b)-1;b;b>>=1){
	if(b&1)ans=ans*tmd%mod;
	tmd=tmd*tmd%mod;
	}
	return ans;
	}

view raw mod inverse.cpp hosted with ❤ by GitHub

另一種模逆元的解法:
計算$A$的模$B$乘法模逆元，可由擴展歐幾里得演算法得到
設$exgcd$擴展歐幾里得演算法的函數，它接受兩個整數$A,B$，輸出三個整數$g,x,y$。
$g,x,y$滿足等式$A \times x+B \times y=g$，且$g=gcd(A,B)$。
當$B=0$時，有$x=1,\; y=0$使等式成立
當$B>0$，在歐基里德算法的基礎上，已知 $$gcd(A,B)=gcd(B,A\%B)$$
先遞迴求出$x^{'},y^{'}$滿足 $$Bx^{'}+(A\%B)y^{'}=gcd(B,A\%B)=gcd(A,B)$$
然後可以將上面的式子化簡得 $$Bx^{'}+(A-(A/B) \times B)y^{'}=gcd(A,B)$$ $$Ay^{'}+Bx^{'}-(A/B) \times By^{'}=gcd(A,B)$$
這裡的除法是整除法，會自動無條件捨去。把含$B$的因式提取一個$B$，可得 $$Ay^{'}+B(x^{'}-(A/B) \times y^{'})=gcd(A,B)$$
故$x=y^{'},\; y=x^{'}-(A/B) \times y^{'}$

若$g=1$，則$A$的模$B$乘法模逆元為$B+x$
$(A \times x+B \times y)\%B=1 \longrightarrow B \times y是B的倍數 \longrightarrow A(x+B)\%B=1 \; (因為x可能小於0)$
總複雜度和歐基里德算法相同，皆為$\ord{logn}$

擴展歐幾里得演算法函數實做:

	template<typename T>
	T exgcd(T a,T b,T &x,T &y){//a*x+b*y=(return)
	if(b){
	T tmd=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return tmd;
	}
	x=1,y=0;
	return a;
	}

view raw exgcd.cpp hosted with ❤ by GitHub