乘法逆元

若,gcd(a,b)=1

则称x为a模p的乘法逆元

我们先来看看有什么用

当输出结果很大时,要模一个mod在输出

(a+b)%mod=a%mod+b%mod

(a-b)%mod=a%mod-b%mod

(a*b)%mod=a%mod*b%mod

(a/b)%mod ... 呃

乘法逆元派上用场了,设b模p的乘法逆元为inv

(a/b)%p=(a*inv)%p=a%p*inv%p

为什么呢

因为b*inv1(mod p)

a/b*b*inv = a*inv  a/b(mod p)

举个例子

11x  1 (mod 7) x=9

(110/10)%7=(110%7)*(9%7)=5*2%7=3

好了,想想怎么求吧

扩展欧几里得

ax1(mod p) 设ax=yp+1,b=-p 则ax+by=1

void exgcd(int a,int b)
{
	if(b==0) g=a,x=1,y=0;
	else{
		exgcd(b,a%b);
		int x1=y,y1=x-a/b*y;
		x=x1,y=y1;
		printf("%d*(%d)+%d*(%d)=%d\n",a,x,b,y,g);
	}
}
inv[a]=(x+p)%p;

 复杂度 O(nlogn)

欧拉定理

欧拉函数

a ^     1(mod p)

a * a ^   1 (mod p)

所以a模p的乘法逆元是a ^ 

复杂度 欧拉函数O(n),快速幂O(logn),O(nlogn)

void init(){//求欧拉函数(phi[i])
	for(int i=2;i<=n;i++){
		if(!p[i]){//是质数 
			p[i]=i,prime[++cnt]=i;//p->最小质因子
			phi[i]=i-1; //phi(prime)=prime-1
		}
		for(int j=1;j<=cnt;j++){
			if(prime[j]>p[i]||prime[j]*i>n) break;//不是最小质因子,或大于n
			p[prime[j]*i]=prime[j];
			phi[prime[j]*i]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);//欧拉函数的性质
		}
	}
}

递推 

for(int i=2;i<=p-1;i++)
    inv[i]=(p-p/i)*inv[p%i]%p;