同余

· · 算法·理论

扩展欧几里得算法

扩展欧几里得算法，也叫 \text{exgcd}。

时间复杂度为 O(\log(a+b))。

long long exgcd(long long a,long long b,long long &x,long long &y){
    if(!b){
        x=1;y=0;
        return a;
    }
    long long d=exgcd(b,a%b,x,y);
    long long z=x;x=y;y=z-y*(a/b);
    return d;
}

使用时，提前定义变量 d,x_0,y_0，调用 d=exgcd(a,b,x0,y0)，程序执行完后 d 就是最大公约数，x_0,y_0 是方程 ax+by=\gcd(a,b) 的一个解。

对于更为一般的方程 ax+by=c，它有解当且仅当 d|c。

乘法逆元

不是所有数都有逆元。

若 b,m 互质，且 b|a，则有整数 x 使 a\div b\equiv a\times x\pmod m，则 x 是 b 的模 m 乘法逆元。

利用费马小定理求乘法逆元

若保证 m 为质数，则除数 b 的模 m 乘法逆元为 b^{m-2}。

需要用到快速幂。

long long qni_fm(long long a,long long p){
    return qmi(a,p-2,p);
}

利用扩展欧几里得算法求乘法逆元

若保证 b,m 互质，则除数 b 的模 m 乘法逆元可通过求解同余方程 b\times x\equiv1\pmod m。

需要用到扩展欧几里得算法。

long long qni_ol(long long a,long long p){
    long long x,y;
    exgcd(a,p,x,y);
    return x;
}

线性同余方程

求 a\times x\equiv b\pmod m 的解相当于求解 a\times x+m\times y=b 的解，使用扩展欧几里得算法求解就可以了。

方程的通解是所有模 m\div\gcd(a,m) 与 x 同余的整数。

中国剩余定理

中国剩余定理，也叫 \text{CRT}。

设 m_1,m_2,…,m_n 两两互质，m=\prod_{i=1}^nm_i，M_i=m\div m_i，t_i 是线性同余方程 M_it_i\equiv 1\pmod {m_i} 的一个解。对于任意 n 个整数 a_1,a_2,…,a_n 的方程组

\begin{cases}x\equiv a_1\pmod {m_1}\\x\equiv a_2\pmod {m_2}\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\x\equiv a_n\pmod {m_n}\end{cases}

有解，解为 x=\sum_{i=1}^na_iM_it_i。

long long CRT(int n,long long *a,long long *m){
    long long sum=0,M=1,x,y;
    for(int i=1;i<=n;i++)
        M*=m[i];
    for(int i=1;i<=n;i++){
        exgcd(M/m[i],m[i],x,y);
        sum+=a[i]*M/m[i]*x%M;
    }
    return (sum%M+M)%M;
}

时间复杂度为 O(n\log(a+b))。

扩展中国剩余定理

扩展中国剩余定理，也叫 \text{EXCRT}。

若在中国剩余定理的基础上无法满足 m_1,m_2,…,m_n 两两互质，则需要使用扩展中国剩余定理。

long long EXCRT(long long n,long long *a,long long *m){
    long long x,y,k,lcm=a[1],ans=m[1],d;
    bool f=1;
    for(int i=2;i<=n;i++){
        m[i]=(m[i]-ans%a[i]+a[i])%a[i];
        d=exgcd(lcm,a[i],x,y);
        if(m[i]%d)
            f=0;
        else
            k=x*(m[i]/d)%a[i];
        ans+=k*lcm;
        lcm=lcm/d*a[i];
        ans=(ans%lcm+lcm)%lcm;
    }
    if(f)
        return ans;
    return -1;
}

若无解会返回 -1，时间复杂度仍是 O(n\log(a+b))。

高次同余方程

BSGS算法

对于方程 a^x\equiv b\pmod p，可以采用 \text{Baby Step,Giant Step} 算法，简称 \text{BSGS}。

需要快速幂。

无解返回 -1，否则返回最小非负整数解。

时间复杂度为 O(\sqrt p)。

long long Baby_Step_Giant_Step(long long a,long long b,long long p){
    map<long long,long long>hash;
    hash.clear();
    b%=p;
    long long t=(long long)sqrt(p)+1,val;
    for(long long j=0;j<t;j++){
        val=(long long)b*qmi(a,j,p)%p; // b*a^j
        hash[val]=j;
    }
    a=qmi(a,t,p); // a^t
    if(!a)
        return b?-1:1;
    for(long long i=0;i<=t;i++){
        val=qmi(a,i,p); // (a^t)^i
        long long j=hash.find(val)==hash.end()?-1:hash[val];
        if(j>=0&&i*t-j>=0)
            return i*t-j;
    }
    return -1;
}

back