No testdata at current.

No submission language available for this problem.

一、同余概述

基本定义和定理

定义1：给定正整数 $m$，若用 $m$ 除两个整数 $a$ 和 $b$ 所得得余数相同，称 $a$ 和 $b$ 对模 $m$ 同余，记作 $a≡b(mod\ m)$

定义2：整数的集合被分为 $m$ 个不同的集合，这些集合被称为模 $m$ 剩余类（同余类）。每个同余类中的任意两个整数都是模 $m$ 同余的。

定理1：$a≡b(mod\ m)$ 当且仅当 $m|(a-b)$

证：令 $a = k_1*m+r$，$b=k_2*m+r$，两式相减有 $a-b = (k_1-k_2)*m$，证毕。

定理2：$a≡b(mod\ m)$ 当且仅当存在整数 $k$，使得 $a =b+km$。

费马小定理：若 $p$ 是质数，则对于任意整数 $a$，有 $a^p≡a(mod\ p)$。视频讲解

欧拉定理：若正整数 $a$, $n$ 互质，则 $a^{\varphi(n)}≡1(mod\ n)$ 其中 $\varphi(n)$ 为欧拉函数。

欧拉定理的推论：若正整数 $a$, $n$ 互质，则对于任意正整数 $b$，有 $a^b≡a^{b\ mod\ \varphi(n)}(mod\ n)$

扩展欧拉定理：若正整数 $a$，$n$ 不互质，则对于任意正整数 $b$，有 $a^b≡a^{b\ mod\ \varphi(n)+\varphi(n)}(mod\ n)$

计算星期几

同余的性质

对于整数 $a$, $b$, $c$ 和自然数 $m$, $n$, 对模 $m$ 同余满足：

自反性：$a≡a(mod\ m)$

对称性：若 $a≡b(mod\ m)$，则 $b≡a(mod\ m)$

传递性：若 $a≡b(mod\ m)$，$b≡c(mod\ m)$，则 $a≡c(mod\ m)$

同加性：若 $a≡b(mod\ m)$，则 $a+c≡b+c(mod\ m)$

同乘性：若 $a≡b(mod\ m)$，则 $ac≡ac(mod\ m)$

一般地，$a≡b(mod\ m)$，$c≡d(mod\ m)$，则有：$ac≡bd(mod\ m)$

同幂性：若 $a≡b(mod\ m)$，则 $a^n≡b^n(mod\ m)$

若 $a\ mod\ p=x$，$a\ mod\ q=x$，其中 $p$,$q$ 互质，则 $a\ mod\ (pq) = x$

---

二、扩展欧几里得算法

欧几里得算法描述： $\forall a, b \in N$, $b\not=0$, $gcd(a, b) = gcd(b, a\% b)$。

定理1：设 $a$ 和 $b$ 不全为 $0$，则存在整数 $x$ 和 $y$，使得 $ax + by = gcd(a, b)$;

证：

当欧几里得算法计算至最后一步时，当 $b = 0$ 时，$gcd(a,b) = a$。因为 $1*a+0*0 =a$，所以 $ax + by = gcd(a, b)$ 存在一组解：$(x, y) = (1, 0)$。

当 $b\not=0$ 时，递归计算 $gcd(b, a\%b)$。假设存在一组 $(x', y')$ 满足 $bx'+(a\%b)y'=gcd(b,a\%b) =gcd(a, b)$.

则，$bx'+(a-a/b*b)y'=gcd(a, b)$，此刻 / 表示整除

整理得到：$ay'+b(x'-a/b*y')=gcd(a, b)$

令 $(x, y) = (y', x'-a/b*y')$，则有 $ax+by=gcd(a,b)$

递归运算至 $b=0$ ，以 $(x,y) = (1,0)$ 归纳计算至 $gcd(a,b)$ 即可。

毕

参考代码

// 求解 ax+by=gcd(a,b) 的一组解 (x, y)，d=gcd(a,b)

void exgcd(int a, int b, int &d, int &x, int &y) {
    int t;
    if (b == 0) { d = a; x = 1; y = 0; }
    else {
        exgcd(b, a%b, d, x, y);
        t = x; x = y; y = t - (a/b)*y;
    }
}

定理2：对于不定方程 $ax+by=c$，当且仅当 $gcd(a,b)|c$ 时，方程有解