同余 | Eternity

“虽然我们相差甚远，但至少初心是一致的。”

同余

定义

$a$ 与 $b$ 同余，当且仅当 $a$ 与 $b$ 除以 $p$ 的余数相同，记作 $a$ 与 $b$ 模 $p$ 同余，写作 $a \equiv b (\mod p)$ 。

同余的性质

若 $a \equiv b (\mod p)$ ，则有 $a + c \equiv b + c (\mod p)$
若 $a \equiv b (\mod p)$ ，则有 $a c \equiv b c (\mod p)$
若 $a \equiv b (\mod p)$ ，且 $c \equiv d (\mod p)$ ，则有 $a \pm c \equiv b \pm d (\mod p)$
若 $a c \equiv b c (\mod p)$ ，且 $(c, m) = 1$ ，那么 $a \equiv b (\mod p)$
若 $a \equiv b (\mod p)$ ，且 $c \equiv d (\mod p)$ ，则有 $a c \equiv b d (\mod p)$
若 $a \equiv b (\mod p)$ ，则有 $a c \equiv b c (\mod p c)$
若 $a$ 和 $b$ 都是整数，且 $d$ 和 $m$ 都是正整数， $d$ 是 $a, b, m$ 中任一公因数，则如果 $a \equiv b (\mod m)$ 成立时，则有 $\frac{a}{d} \equiv \frac{b}{d} (\mod \frac{p}{d})$
若 $a$ 和 $b$ 都是整数，且 $d$ 和 $m$ 都是正整数，且 $d | m$ ，则如果 $a \equiv b (\mod m)$ 成立时，则有 $a \equiv b (\mod d)$ 。
若 $a$ 和 $b$ 都是整数，且 $d$ 和 $m$ 都是正整数，如果 $a \equiv b (\mod m)$ 成立时，则有 $(a, m) = (b, m)$ ，且若如果 $d$ 能够整除 $a, b, m$ 中的任意一个， $d$ 也就能整除 $a, b$ 中的另一个。

扩展欧几里得算法

若 $(a, b) = d$ ，那么对于方程 $a x + b y = d$ 的解有一组特殊解为 $x = x_{0}, y = y_{0}$ ，那么该方程的通解为 $x = x_{0} + \frac{b}{d} \times t, y = y_{0} - \frac{a}{d} \times t$ ，而我们用这个通解来逆向推出 $g c d$ ，因为我们有欧几里得定理：

$(a, b) = d$ ，则有 $(b, a mod b) = d$

那么就会推出： $d = a \times y_{1} + b \times (x_{1} - y_{1} \times \frac{a}{b})$

在这个算式中满足： $x = y_{1}, y = x_{1} - \frac{a}{b} \times y_{1}$

扩欧解同余方程

对于方程 $a x \equiv 1 (\mod b)$ ，已知 $a$ 与 $b$ ，求出最小的 $x$ 。

LuoguP1082

妥妥的扩欧模板题：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long LL;
using namespace std;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
LL a,b,x,y;
inline void underExgcd(LL a,LL b)
{
    if(!b)
    {
        x=1,y=7;            //一对特殊解
        return ;
    }
    underExgcd(b,a%b);
    LL tx=x;
    x=y;
    y=tx-a/b*y;
}
int main()
{
    // freopen("exgcd.in","r",stdin);
    // freopen("exgcd.out","w",stdout);
    underRead(a),underRead(b);
    underExgcd(a,b);
    x=(x%b+b)%b;
    printf("%lld",x);
    return 0;
}
/*
3 10
*/

中国剩余定理

LuoguP1495曹冲养猪

有一个同余方程组满足：

\begin{matrix} {\begin{matrix} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ x \equiv a_{3} (\mod m_{3}) \\ x \equiv a_{4} (\mod m_{4}) \\ x \equiv a_{5} (\mod m_{5}) \\ . . . . . . \\ x \equiv a_{k} (\mod m_{k}) \end{matrix} \end{matrix}

，求出最小的 $x$ 。

思路

设 $M = m_{1} m_{2} m_{3} \dots m_{k}$ ，令 $M_{i} = \frac{M}{m_{i}}$ ， $t_{i}$ 是 $M_{i}$ 的逆元，有 $M_{i} t_{i} \equiv 1 (\mod m)_{i}$

则 $x = \sum_{i = 1}^{k} a_{i} M_{i} t_{i}$

则可构造特殊解 $x_{0} = x + k \times M$

最小正整数解即为 $x_{m i n} = x_{0} mod M$

P3868 AC Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long LL;
using namespace std;
const int MAXN=1e5+1;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int N;
struct Node
{
    LL type,mod;
}Num[MAXN];
LL M[MAXN],Mul=1,Mi[MAXN],X;
inline void underExgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1,y=0;
        return ;
    }
    underExgcd(b,a%b,x,y);
    LL z=x;x=y;y=z-y*(a/b);
}
int main()
{
    // freopen("china.in","r",stdin);
    // freopen("china.out","w",stdout);
    underRead(N);
    for(int i=1;i<=N;++i)
    {
        underRead(Num[i].type),underRead(Num[i].mod);
        Mul*=Num[i].type;
    }
    for(int t=1;t<=N;++t)
    {
        Mi[t]=Mul/Num[t].type;
        LL x=0,y=0;
        underExgcd(Mi[t],Num[t].type,x,y);
        X+=Num[t].mod*Mi[t]*(x<0?x+Num[t].type:x);
    }
    printf("%lld",X%Mul);
    return 0;
}
/*
3
3 1
5 1
7 2
*/