同余 && 逆元

参考及引用大佬博客
https://www.cnblogs.com/kongbursi-2292702937/p/10582258.html
https://blog.csdn.net/tobeyours/article/details/79619333

同余

定义
给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b（mod m），假设，100-60除以8正好除尽，则100和60对于模数8同余

主要性质
加法：（a+b）%d=（a%d+b%d）%d
减法：（a-b+mod）%mod；

---

逆元

定义
当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：
设c是b的逆元，则有b * c≡1（mod m）；
则（a/b）%m = （a/b）* 1%m = （a/b） * b * c%m = a * c（mod m）;
即a/b的模等于a*b的逆元的模；

（1）费马小引理
前提：a和p互质

代码实现：快速幂

long long quickpow(long long a,long long b){
    if(b<0)
        return 0;
    long long ret=1;
    a%=mod;
    while(b){
        if(b&1){ //如果是奇数
            ret=(ret*a)%mod;
        }
        b>>=1;
        a=(a*a)%mod;
    }
    return ret;
}

long long inv(long long a){
    return quickpow(a,mod-2);
}

补充：快速幂+快速乘
当a,b很大的时候 在10^9时，用常规的方法就容易超时

long long quickmul(long long a,long long b,long long mod){
    long long ret=0;//这里是初始化为0
    while(b){
        if(b&1){ //如果是奇数
            ret=(ret+a)%mod;
        }
        b>>=1;
        a=(a*a)%mod;
    }
    return ret;
}

long long quickpow(long a,long b,long mod){
    long long ret=1;
    while(b){
        if(b&1){
            ret=quickmul(ret,a,mod);
        }
        a=quickmul(a,a,mod);
        b>>=1;
    }
    return ret;
}

（2）扩展欧几里得算法

辗转相除法：

算法证明：a和m互质

求逆元：

ll extend_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    else {
        ll r = extend_gcd(b, a % b, y, x);
        y -= x * (a / b);
        return r;
    }
}
ll inv(ll a, ll n) {
    ll x, y;
    extend_gcd(a, n, x, y);
    x = (x % n + n) % n;
    return x;
}