前言

都是一些零散的知识，梦到哪里记到哪。。。

1.最大公约数算法原理

  • 首先，老师上课讲过，但是好像并没有听懂，今天重刷洛谷时候感觉对这方面不是很熟。
    这个方法来自欧几里得的辗转相除法。代码实现如下：
1
2
3
gcd(a,b){
    return b == 0 ? a : gcd(b, a % b);
}

辗转相除法：

  • 实际上，这是高等代数讲过的问题，就是最大公约数和最大公约数的区别。先回忆一下高代中的知识。

  • 定理：
    在多项式环 $P[x]$ 中，任意两个多项式 $f(x)$ 和 $g(x)$ 都存在最大公因式。
    而且，$f(x)$ 和 $g(x)$ 的任意一个最大公因式 $d(x)$ 都可以表示为 $f(x)$ 和 $g(x)$ 的线性组合，即存在 $u(x), v(x) \in P[x]$，使得：

$$
d(x) = u(x)f(x) + v(x)g(x)
$$

  • 证明如下图所示：
    1.jpg
    由上述定理，我们可以知道f(x),g(x)的最大公因式一定存在，接下来我们看用辗转相除法的原理证明（题外话,,这成高代笔记了。。）：
    2.jpg
    小红书大佬的辗转相除法证明：
    3.jpg
    那我们回过头看，令 a%b=r，这段代码的含义就是如果 b 不等于0，函数就返回 gcd(b,r)，直到b=0，此时的a就是图二中的 rs(x).
1
2
3
gcd(a,b){
    return b == 0 ? a : gcd(b, a % b);
}

2.同余原理

定义：

  • 如果两个整数 $a$ 和 $b$，以及一个正整数 $m$，满足 $a \equiv b \pmod{m}$，则称 $a$ 与 $b$ 在模 $m$ 意义下同余。
    也就是说，$a$ 和 $b$ 除以 $m$ 后余数相同，或者 $m$ 能整除 $a-b$。
    举例：
    $17 \equiv 5 \pmod{12}$，因为 $17 - 5 = 12$ 能被 $12$ 整除。
    相当于：$a-b=km$，或者$a=b+km$.

性质：

  • 同余关系具有传递性、对称性和自反性。（离散数学）
  • 如果 $a \equiv b \pmod{m}$，则 $a + c \equiv b + c \pmod{m}$，$a \cdot c \equiv b \cdot c \pmod{m}$。

应用：

  • 常用于简化大数运算，比如快速判断某个数能否被整除。
  • 在密码学、算法竞赛、程序设计等领域广泛应用。

例题：

  • 2003年5月9日是星期五，问第 $2^{2003}$ 天是星期几？
    解题思路：

    一周有 7 天，星期几每 7 天循环一次，所以只需计算 $2^{2003}$ 除以 7 的余数。

    计算 $2^{2003} \bmod 7$：

    注意到 $2^3 \equiv 1 \pmod{7}$，所以 $2^{2003} = 2^{3 \times 667 + 2} = (2^3)^{667} \times 2^2 \equiv 1^{667} \times 4 \equiv 4 \pmod{7}$。

    推算星期几：

    第 1 天是星期五，第 $2^{2003}$ 天是星期五后的第 4 天：

    • 星期五 + 1 天 = 星期六
    • 星期五 + 2 天 = 星期日
    • 星期五 + 3 天 = 星期一
    • 星期五 + 4 天 = 星期二

    答：第 $2^{2003}$ 天是星期二。

编程题目：

lianxi.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;

int main() {
    int x, n;
    cin >> x >> n;
    int days = 0;
    for (int i = 0; i < n; ++i) {
        int currentDay = (x + i - 1) % 7 + 1; 
        if (currentDay != 6 && currentDay != 7) {
            days += 250;
        }
    }
    cout << days << endl;
    return 0;
}
  • 上述代码为题解，其中，关键点是天数的确定
1
int currentDay = (x + i - 1) % 7 + 1;
  • 关键就在于这行代码，这里通过对 7 取模（% 7），实现了星期的循环计算。因为一周有 7 天，星期几每 7 天循环一次，所以用模运算可以得到当前是星期几，这正是同余原理在实际编程中的应用。现在我们来仔细解读这段代码
    • x+i-1：
      x 是起始星期几，比如星期五就是 5。
      i 是循环变量，表示第几天（第 0 天、第 1 天……）。
      x + i - 1 这样写是为了让第 0 天就是起始星期几，第 1 天是起始星期几的下一天，以此类推。
    • 如果没有 -1，比如 currentDay = (x + i) % 7 + 1，那么当 i = 0 时，结果是 x + 0，也就是第 1 天是星期 x+1，这样会错位一天。
    • +1：因为 % 7 得到的是 0-6，而星期几通常用 1-7 表示，所以最后加 1，把结果变成 1-7。