逆元
基本的逆元求法
求某个数的逆元。
对于除法的逆元，乘法的倪源直接求：相乘取模，在处理除法的逆元的时候，我们假定 :
a/b = x (mod p) (1)
a*b_1 = x (mod p) (2)
b*b_1 =1 (mod p)（3）
我们可以在1式的分子和分母同时乘以b_1,，(1)式可以变成(2)式。那么求解x的问题就变成了求解b_1;
首先我们用扩展欧里几德的方法来求逆元
我们对（3）式进行如下变换：
b* Y = 1 (mod p ) <==> b* Y+ p* X = 1 的一组解
我们定义第二个等式的右边为 c , c必须满足 是 gcd(a,b)的倍数，因为 b , p 都是gcd(p,b)的倍数，得到一个重要结论，只有两个数互质才有逆元。
接下来我们证明另一个性质：X,Y的解可有有扩展欧里几德算法来求得。代码6如下：
//代码段 6
#include<iostream>
#define ll long long
using namespace std;
//x的系数是被模的数，y的系数是模数，根据欧里几德的运算，我们可以找一组解
//每次回溯时，x的值被y取代，y的值为px-a/b*y,讲道理，a多数大于b
//x小于y
ll x,y;
ll exgcd(ll a,ll b){
if(b==0){
x=1;y=0;//创造一组解；
return a;
}
else{
exgcd(b,a%b);
ll tx=x;
x=y;
y=tx-a/b*y;
}
}
int main() {
ll a,b,t;
cin>>a>>b;
t=exgcd(a,b);
if(t%1!=0) return 0;
cout<<(x%b+b)%b<<endl;
return 0;
}
根据上述的一个重要结论，存在逆元的条件是 两个数互质，我们根据这一性质可以引入费马定理：
a ^(p-1) = 1 (mod p ) if( gcd(a, p) == 1 )
==> a_1 = a^(p-2) //快速幂做法
代码间上文代码段3，详见下文
小费马定理扩展: 欧拉定理
1.a^f(p) = 1 (mod p ) if ( gcd(a,p)==1 ) ==> a^b = a^(b % f(p) ) mod( p )
我们先把大部分次幂用来凑1 , 即是：
**af(p)*x * ar == ar (mod p)
2.ab = ab ( gcd(b,p)!=1 , b< f(p)) (mod p)
3. ab = ar * af(p) (mod p ) if( gcd(a,p)!=1, b>=f(p) )
在蓝桥杯 -子集选取 一题中就设计的对幂指数去模；
我们来复习一下欧拉函数，和唯一分解定理。
唯一分解定理
任何一个数都可以分成若干个质数的幂次积如下：
**K= a1p1 * a2p2 * a3p3 * ......* anpn **
我们可以通过分解，我们直接贴代码段7如下
#include<iostream>
#include<vector>
using namespace std;
vector< pair<int ,int> > vt;//可以转成两个数组来记录
int main(){
int n;
cin>>n;
int cnt=2,ti=0;
while(n){
while(n%cnt==0){
ti++;
n/=cnt;
}
if(ti!=0){
vt.push_back(make_pair<cnt,ti>);
ti=0;
}
cnt++;
}
}
**但是如果n 含有一个特别大的质数p，那么cnt 需要增加到p ，循环结束，显然这样做的代价太大了，我们可以通过分析将复杂度将至根号级别，证明如下：
如果p = p1* p2 其中必有一个小于等于sqrt(q) 若cnt*cnt>p则 p 必然是个素数；
修改代码段7.1如下:
int cnt=2,ti=0;
while(n){
while(n%cnt==0){
n/=cnt;
ti++;
}
if(ti!=0) vt.push_back(make_pair<cnt,ti>),ti=0;
cnt++;
if(cnt*cnt>n) break;
}
if(n!=1) vt.push_back(make_pair<n,1>);//最后一个数也是他的因子
如果那当数字非常多的时候可以进行常数优化，我们可以先用线性筛把素数筛出来，然后直接来除以素数； 修改代码段7.2如下：
int ss[100000],n,cnt=0;
bool vis[100000]={0};
void pre(int k){
vis[1]=true;
for(int i=2;i<=k;i++){
if(!vis[i]) ss[cnt++]=i;
for(int j=0;ss[j]*i<=k&&j<cnt;j++){
vis[ss[j]*i]=1;
if(i%ss[j]==0) break;
}
}
}
int p1=0,ti=0;
while(n){
while(n%ss[p1]==0){
ti++;
n/=ss[p1];
}
if(ti!=0) vt.push_back(make_pair<ss[p1],ti>),ti=0;
p1++;
if(ss[p1]*ss[p1]>n) break;
}
if(n!=1) vt.push_back(make_pair<n,1>);
欧拉函数
公式
**N=p1c1 * p2c2 * p3c3 * .....* pncn **
方法1:容斥原理
欧拉函数指的是小于N且与N互质的数，互质就是没有公因子，我们把N个数中是p1,p2,....,pn的倍数的数全部删掉就是N的欧拉函数，即： N- N/pi+N/pipj-N/pipjpk... 经过整理的到
N =N*(1-1/p1)* (1-1/p2)* (1-1/p3)* ... * (1-1/pn)
证法二： 根据质数的欧拉函数
f(N)=N-1 (if N 为质数)
f(N)=f(p1k1)*....* f(pnkn)
其中f(p1k1 ) = pk1 -pk1-1=p1k1 *(1-1/p1)
因为p1的倍数有p1k1-1 个
代码段8如下：
//在代码⑦的基础上修改就可以了
int sum=n,p1=2;
while(n){
if(n%p1==0){
sum=sum*(p1-1)/p;
while(n%p1==0) n/=p1;
}
p1++;
if(p1*p1>n) break;
}
sum=sum*(n-1)/n;
扩展小结
- 求更号k的等效数，求x2 = k (mod p ) ,x为k的一个等效解，只能一个个尝试。
- 唯一分解定理的扩展，一个数的因子个数和因子和
唯一分解定理的扩展：所有因子和与因子个数
根据唯一分解式 :
**N=p1c1 * p2c2 * p3c3 * .....* pncn **
对于每个质数我们可以有0，pi, pi2 , pi3 , ... , pici 中选择方法。所以容易得到个数函数：
S(N)=(1+c1)*(1+c2)*...*(1+cn)
他们的和我们可以根据乘法原理来设计：就是n个位置上的数的乘积，而且每个位置的的数是多变的；
可以推导出这个乘法式子
T(N)=(P10 + P11 + P12 + ... + P1c1 )(P20 + P21 + P22 + P23 + ... + P2c2).....(Pn0 + Pn1 + +Pn2 + ... + Pncn )
根据等比数列求和公式
Pi0 + pi1 +....+ pic1 = (pici+1 -1)/(pi-1)
代码段9 如下：
#include<iostream>
#define ll long long
using namespace std;
ll dcpsum(ll x){
ll ans=1;
ll cnt=1,tem;
while(cnt<=n){
if(n%cnt==0){
tem=1;
while(n%cnt==0){
tem*=cnt;
n/=cnt;
}
ans*=(tem*cnt-1)/(cnt-1);
}
cnt++;
if(cnt*cnt>n) break;
}
if(n!=1) ans*=(n+1);
return ans;
}
线性求逆元
适用于小于一个较大的质数的一堆数的逆元求解。
证明
p=ki+r(r<i)
ki+r=0(mod p)
kr_1+i_1=0(mod p)
i_1=-kr_1(k=p/i);这样可以由较小的推较大的逆元。
i_1正整数化，可以选择i_1=(p-p/i)r_1%p;或者i_1=-(p/i)r_1%p+p%p
代码1如下：
//代码段1
#include<iostream>
using namespace std;
int main(){
int p=1e9+9;
long long inv[1000000009];
inv[0]=0,inv[1]=1;
for(int i=2;i<p;i++){
inv[i]=(p-p/i)*in[p%i]%p;
}
}
求组合数的逆元
组合数C(n,m),可以展开成阶乘的形式： n!/(n-m)!/m!, 可以看成n!乘以inv((n-m)!)*inv(m!),对于所有组合数我们只要预处理出来阶乘的逆元就可以了，对于阶乘的逆元因为存在1/（n+1)!*(n+1)=1/n!,所以inv(n!)*inv(n+1)=inv((n+1)!)
代码2:
//代码段 2
#include<iostream>
#define ll long long
using namespace std;
ll ha=1r9+9;
const int N=1e9；
ll fac[N]，inv[N];//阶乘的逆元和阶乘倒数的逆元
ll C(int n,int m){
return fac[n]*inv[n-m]*inv[m]%ha;
}
void pre(int n){
fac[1]=1;for(int i=2;i<=n;i++) fac[i]=fac[i-1]*i%ha;
//求阶乘的逆元
inv[1]=1;for(int i=2;i<=n;i++) inv[i]=(ha-ha/i)*inv[ha%i]%ha;
//线性求逆元
inv[0]=1;for(int i=1;i<=n;i++) inv[i]=inv[i-1]*inv[i]%ha;
//求阶乘的逆元
}
### 求单个数的逆元（logN）
小费马定理加上快速幂
证明
if(gcd(a,b)==1)(b>a)
a^(b-1)=1 (mod b)
so： a_1=a^(b-2);
这就是小费马定理；
代码3
//代码段3
#include<iostream>
#define ll long long
using namespace std;
const int ha=;
ll pd(ll a,int b){
ll res=1;
while(b){
if(b&1) res=res*a%ha;
b>>=1;
a=a*a%ha;
}
return res;
}
大组合数求模
利用卢卡斯定理，这里直接介绍结论
C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p;
这里的n,m可能还是很大，所以可以用递归的迭代形式
//代码段 5
#include<iostream>
#define ll long long
using namespace std;
const int ha=;
ll pd(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%ha;
b>>=1;
a=a*a%ha;
}
return res;
}
ll comp(ll a,ll b){
if(a<b) return 0;
if(a==b) return 1;
if(b>a-b) b=a-b;
ll ans=1,ca=1,cb=1;
for(int i=0;i<b;i++0{
ca=ca*(a-i)%ha;
cb=cb*(b-i)%ha;
}//求组合数
ans=ca*pd(cb,ha-2)%ha;//利用小费马求阶乘的逆元，如果p比较小，n,m特别大，可以预处理出组合数的逆元。
return ans;
}
ll lucas(ll a,ll b){
ll ans=1;
while(a&&b){
ans=ans*comp(a%ha,b%ha)%ha;
a/=m;b/=m;
}
return ans;
}
//卢卡斯定理的递归形式。
ll lucas2(ll a,ll b){
return b?lucas2(a/ha,b/ha)*comp(a%ha,b%ha)%ha:1;
}
复杂度分析
在线性求组合数的逆元的时候是O(ha)+log(ha,m,n);
总体复杂度O(ha)