同余

JohnJoeZhu · 2019-12-04 21:33:16 · 个人记录

同余（2019.12.4）

(为了巩固Latex，本篇手打)

讲解+题

题单

准备定理

a\equiv b \pmod{m}$ 当且仅当 $m| \left( {a-b} \right)
a\equiv b \pmod{m}$ 当且仅当存在$k$使得 $a=b+km
费马小定理当p为质数时，a^{p-1}\equiv 1 \pmod{p}
欧拉定理若a\perp n (a,n为正整数)，则a^{\varphi(n)}\equiv 1\pmod{n}
欧拉定理的推论若a\perp n (a,n为正整数)，则对于任意正整数b，有a^b\equiv a^{b\bmod \varphi(n)}\pmod{n}

准备性质

对于整数a,b,c和自然数m,n,对m取模满足

自反性 a \equiv a\pmod{m}
对称性若a \equiv b\pmod{m},则b\equiv a\pmod{m}
传递性若a \equiv b\pmod{m},b\equiv c\pmod{m},则a\equiv c\pmod{m}
同加性若a \equiv b\pmod{m},则a+c \equiv b+c \pmod{m}
同乘性若a \equiv b\pmod{m},则ac \equiv bc \pmod{m}
一般情况下，若a \equiv b\pmod{m},c\equiv d\pmod{m},则ac \equiv bd \pmod{m}
同幂性若a \equiv b\pmod{m},则a^n\equiv b^n \pmod{m}
互质性若a \bmod p=x,a \bmod q=x,且p\perp q,则a \bmod(pq)=x

扩展欧几里得算法

贝祖定理当a,b不全为0时，存在整数x,y,使得

\color{green}ax+by=gcd(a,b)

欧几里得算法 \forall a,b\in N,b\ne 0有

gcd\left(a,b\right)=gcd\left(b,a\bmod b\right)

接下来，我们来求解方程

ax+by=gcd(a,b)

当b\ne 0时，设存在一对整数x',y'，满足

bx'+\left(a\bmod b \right)y'=gcd(b,a \bmod b)=gcd(a,b)

那么

bx'+(a-\lfloor \frac{a}{b} \rfloor \times b)y'=gcd(a,b)

去括号，得

bx'+ay'-(\lfloor \frac{a}{b} \rfloor \times b)y'=gcd(a,b)

把a,b提出来，得

ay'+b(x'-\lfloor \frac{a}{b} \rfloor \times y')=gcd(a,b)

所以，

\color{red} x=y',y=x'-\lfloor \frac{a}{b} \rfloor*y'

当b=0时，x=1,y=0

所以，我们就可以求Exgcd(a,b)了

\\代码
int x,y;
int Exgcd(int a,int b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    //if(b!=0)
    int gcd=Exgcd(b,a%b);
    int t=x;
    x=y;
    y=t-a/b*y;
    return gcd;
}

接下来，我们来求解不定方程

\color{green}ax+by=c

当gcd(a,b)|c时，设g=gcd(a,b),a'=a/g,b'=b/g,c'=c/g

先利用Exgcd(a',b')求解

\color{darkgreen}a'x'+b'y'=gcd(a',b')=1

转化，得

a'c'x'+b'c'y'=c'

a'gc'x'+b'gc'y'=c'g

合并，得

ac'x'+bc'y'=c

所以该方程有一组解为

\color{darkred}x_0=c'x',y_0=c'y'

因为

a'x+b'y=c' \Leftrightarrow a'x \equiv c'\pmod{b'}

所以该不定方程的通解为

\color{red}x=x_0+b'\times t,y=y_0 - a'\times t (t\in Z)

当gcd(a,b)\not|c时，无解

例题

P1516 青蛙的约会建立不定方程，求最小解

P2421 荒岛野人建立不定方程，求可行最小解

线性同余方程

定义：已知整数a,b,m，求整数x满足\color{green}ax\equiv b \pmod m

推导过程：

a \times x \equiv b \pmod m

\Downarrow

a \times x -b \equiv 0 \pmod m

\Downarrow

\color{darkgreen}a\times x + m \times y =b

因此，我们只需要求解上面的不定方程即可

定理1：对于多异解
定理2：\color{red}ax\equiv 1\pmod m有解当且仅当\color{red}a\perp m

乘法逆元

若整数b\perp p,且b|a,则存在一个整数x,使得\frac{a}{b}\equiv a \times x \pmod p,称x为b在模p意义下的乘法逆元，记为b^{-1}\pmod p

定理：b\times b^{-1}\equiv 1 \pmod p

费马小定理法：若p是质数，\color{red}b^{-1}=b^{p-2} \pmod p

扩展欧几里得法： b^{-1}\pmod p是\color{red}b\times x \equiv 1 \pmod p的最小正整数解

线性算法：

首先我们有, 1^{-1}\equiv 1 \pmod p

然后设 p=k*i+r(1<r<i<p)

也就是 k 是 p / i 的商， r 是余数

再将这个式子放到 \pmod p 意义下就会得到：

k*i+r \equiv 0 \pmod p

然后乘上 i^{-1},r^{-1} 就可以得到:

k*r^{-1}+i^{-1}\equiv 0 \pmod p

i^{-1}\equiv -k*r^{-1} \pmod p

i^{-1}\equiv -\lfloor \frac{p}{i} \rfloor*(p \bmod i)^{-1} \pmod p

因为i^{-1}>0,所以转正数，得

i^{-1}\equiv p-\lfloor \frac{p}{i}\rfloor \times (p \bmod i)^{-1} \pmod p

因为

p= p*(p \bmod i)^{-1} \equiv 0 \pmod p

所以

i^{-1}\equiv (p - \lfloor \frac{p}{i} \rfloor)\times(p \bmod i)^{-1} \pmod p

模板

\\代码实现
inv[1] = 1;
for(int i = 2; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;

BSGS

题单

求A^x\equiv B\pmod C(A\perp C)

设$A^{i*\sqrt{C}-j}\equiv B\pmod C

则有A^{i*\sqrt{C}}\equiv A^j*B\pmod C

暴力预处理左边与右边，用map记录（或者hash）

int BSGS(int a,int b,int mod)
{
    if(a==0&&b) return -1;
    if(a==0&&b==0) return 1;
    if(b==1) return 0;
    map<int,int>hash;
    hash.clear();
    int sqrtmod=sqrt(mod)+1;
    int c=b%mod;
    for(int i=0;i<sqrtmod;i++)
    {
        if(!hash[c]) hash[c]=i+1;
        c=mul(c,a,mod)%mod;
    }
    int d=power(a,sqrtmod,mod),e=d;
    for(int i=1;i<=sqrtmod;i++)
    {
        int ans=hash[e];
        if(ans) return i*sqrtmod-(ans-1);
        e=mul(e,d,mod)%mod;
    }
    return -1;
}

数论乱搞题

P2818 天使的起誓 n \bmod m支持边读边模，读一次模一次