数论(2)---逆元

数论(2)--------求逆元

1.exgcd算法

适用于个数不多但是mod很大的时候
时间复杂度：O(log n)

ll exgcd(ll a,ll b,ll &x,ll &y){//扩展欧几里得算法  
    if(a == 0 && b == 0) return -1;
        if(b==0){  
        x=1,y=0;  
        return a;  
    }  
    ll res=exgcd(b,a%b,y,x);  
    y-=a/b*x;  
    return res;  
}  
ll inv(ll a){//求a在mod下的逆元，不存在逆元返回-1  
    ll x,y;  
    ll ans = exgcd(a,mod,x,y);  
    return ans == 1 ? (x%mod+mod)%mod : -1;  
}

2.递归求逆元

mod数是素数
时间复杂度：O(logmod)

//只能求a < m 的情况，a、m互质
ll inv(ll a){  
    //if(a > mod) swap(a,mod);  
    if(a == 1) return 1;  
    return inv(mod%a,mod)*(mod-mod/a)%mod;  
}

3.欧拉函数求解

在mod是个素数的时候用，并且方便
时间复杂度：O(logmod)

ll f_pow(ll x,ll n){
    ll res=1;
    while(n){
        if(n&1) res=res*x%mod;
	x=x*x%mod;
	n>>=1;
    }
    return res;
}
ll inv(ll a,ll mod){  
    return f_pow(a,mod-2);  
}

4.逆元线性预处理

求1...n之间每一个数字的逆元，如果都使用上面的算法将会达到\(O(n log p)\)，而利用递推的的方式可以\(O(n)\)的处理这个问题。
如下:
\(i^{-1} = -\lfloor \frac{p}{i} \rfloor* (p\mod i)^{-1}\mod p\)
(图论选手完全看不懂就是了)

int inv[N];
void init_inv(){
    inv[1] = 1;
    for(int i = 2;i < N;i++)
    inv[i] = (mod-mod/i)*inv[mod%i]%mod;
}