03 最大公约数 GCD 学习目标 理解 gcd⁡(a,b)\gcd(a,b)gcd(a,b)、互质，以及“互质为什么决定逆元是否存在”。 1. 最大公约数 12 的因数有 1,2,3,4,6,121,2,3,4,6,121,2,3,4,6,12，18 的因数有 1,2,3,6,9,181,2,3,6,9,181,2,3,6,9,18。 最大公共因数是 6，所以： gcd⁡(12,18)=6\gcd(12,18)=6 gcd(12,18)=6 2. 什么叫互质 若 gcd⁡(a,b)=1\gcd(a,b)=1gcd(a,b)=1，称 a,ba,ba,b 互质。 注意：互质不代表两个数都必须是素数。例如 gcd⁡(8,15)=1\gcd(8,15)=1gcd(8,15)=1。 3. 素数的一个重要性质 若 ppp 是素数，且 1≤a<p1\le a<p1≤a<p，那么一定有： gcd⁡(a,p)=1\gcd(a,p)=1 gcd(a,p)=1 因为 ppp 的正因数只有 1 和 ppp，而 a<pa<pa<p。 4. 为什么 GCD 和逆元有关 后面会证明： > aaa 在模 mmm 下存在乘法逆元，当且仅当 gcd⁡(a,m)=1\gcd(a,m)=1gcd(a,m)=1。 因此求 gcd 其实是在判断“能不能做模意义下的除法”。 5. 基本性质 gcd⁡(a,b)=gcd⁡(b,a)\gcd(a,b)=\gcd(b,a) gcd(a,b)=gcd(b,a) gcd⁡(a,0)=∣a∣\gcd(a,0)=|a| gcd(a,0)=∣a∣ 若 d=gcd⁡(a,b)d=\gcd(a,b)d=gcd(a,b)，则 d∣ad\mid ad∣a 且 d∣bd\mid bd∣b。 6. 暴力做法 下一节会学习更快的欧几里得算法。 7. 小练习 1. gcd⁡(24,36)\gcd(24,36)gcd(24,36) 2. 8 和 21 互质吗？ 3. 若 p=17p=17p=17 且 1≤a<171\le a<171≤a<17，gcd⁡(a,17)\gcd(a,17)gcd(a,17) 是多少？ 答案 1. 12 2. 互质 3. 1

02 同余 学习目标 理解 a≡b(modm)a\equiv b\pmod ma≡b(modm) 的含义，掌握同余的加、减、乘性质，并知道为什么不能随便“约掉”。 1. 从时钟理解“模” 15 点在 12 小时制里相当于 3 点，所以 15≡3(mod12)15\equiv3\pmod{12}15≡3(mod12)。 2. 同余的含义 a≡b(modm)a\equiv b\pmod ma≡b(modm) 表示 a,ba,ba,b 除以 mmm 后余数相同。 更正式地说： a≡b(modm)  ⟺  m∣(a−b)a\equiv b\pmod m \iff m\mid(a-b) a≡b(modm)⟺m∣(a−b) 例如 17≡2(mod5)17\equiv2\pmod517≡2(mod5)，因为 17−2=1517-2=1517−2=15，而 5∣155\mid155∣15。 3. 完全剩余系 模 mmm 时，每个整数都能归到 0,1,…,m−10,1,\dots,m-10,1,…,m−1 中的一个余数类。 所以竞赛里讨论“模 mmm 的解”时，常只看 0≤x<m0\le x<m0≤x<m。 4. 同余可以做什么 若 a≡b(modm)a\equiv b\pmod ma≡b(modm)，c≡d(modm)c\equiv d\pmod mc≡d(modm)，则： a+c≡b+d(modm)a+c\equiv b+d\pmod m a+c≡b+d(modm) a−c≡b−d(modm)a-c\equiv b-d\pmod m a−c≡b−d(modm) ac≡bd(modm)ac\equiv bd\pmod m ac≡bd(modm) 5. 不能随便除 例如 2×1≡2×4(mod6)2\times1\equiv2\times4\pmod62×1≡2×4(mod6)，但不能直接约掉 2 得到 1≡4(mod6)1\equiv4\pmod61≡4(mod6)。 模运算里的“除法”需要额外条件。后面学习乘法逆元后，我们会把“除法”改写成“乘逆元”。 6. 小练习 1. 23≡?(mod7)23\equiv ?\pmod723≡?(mod7) 2. 14≡2(mod6)14\equiv2\pmod614≡2(mod6) 是否成立？ 3. 若 a≡4(mod7)a\equiv4\pmod7a≡4(mod7)，则 a2≡?(mod7)a^2\equiv ?\pmod7a2≡?(mod7) 答案 1. 222 2. 成立 3. 222

01 整除 学习目标 理解 a∣ba\mid ba∣b 的含义，掌握因数、倍数和整除的基本性质，为同余和 gcd 做准备。 1. 从“平均分没有剩余”开始 12 个苹果平均分给 3 个人，每人 4 个，没有剩余，所以 3 能整除 12，记作 3∣123\mid123∣12。 a∣ba\mid ba∣b 的正式含义是：存在整数 kkk，使 b=akb=akb=ak。 例如 6∣246\mid246∣24，因为 24=6×424=6\times424=6×4；但 5∤175\nmid175∤17，因为 17 除以 5 有余数。 2. 因数和倍数 若 a∣ba\mid ba∣b： * aaa 是 bbb 的因数； * bbb 是 aaa 的倍数。 3. 常用性质 若 a∣ba\mid ba∣b 且 a∣ca\mid ca∣c，则 a∣(b+c)a\mid(b+c)a∣(b+c)、a∣(b−c)a\mid(b-c)a∣(b−c)。 若 a∣ba\mid ba∣b，则对任意整数 kkk，都有 a∣bka\mid bka∣bk。 若 a∣ba\mid ba∣b 且 b∣cb\mid cb∣c，则 a∣ca\mid ca∣c。 4. 为什么算法竞赛要学 以后会看到 m∣(a−b)m\mid(a-b)m∣(a−b)。它等价于 a≡b(modm)a\equiv b\pmod ma≡b(modm)，这正是同余的定义。 所以知识链的第一步是： > 整除 → 同余 → gcd → 逆元 5. 易错点 a∣ba\mid ba∣b 不是除法 a/ba/ba/b，而是“aaa 整除 bbb”。 6. 小练习 1. 7∣427\mid427∣42 吗？ 2. 6∣356\mid356∣35 吗？ 3. 若 5∣a5\mid a5∣a 且 5∣b5\mid b5∣b，则 5∣(a+b)5\mid(a+b)5∣(a+b) 吗？ 答案 1. 是 2. 否 3. 是

BRUUUUUUUUUUUUUUUUUUUUUUHAC修勾魔了想要点思路直接给我几千字论文是吧有点意思。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。瞬间就不想做了。。。。。。。。。。。。。。。。。。。。。

333

看第一行

#include <iostream> using namespace std; int R, C; char grid[20][20]; // dfs(x,y): 当前在(x,y)，返回从(x,y)到终点的路径数 int dfs(int x, int y) { // 到达右下角，找到1条方案 if (x == R-1 && y == C-1) { return 1; } int res = 0; // 枚举所有可以跳过去的点 i>x, j>y for (int i = x+1; i < R; i++) { for (int j = y+1; j < C; j++) { // 颜色不同才能跳 if (grid[i][j] != grid[x][y]) { res += dfs(i, j); } } } return res; } int main() { cin >> R >> C; for (int i = 0; i < R; i++) { cin >> grid[i]; } cout << dfs(0, 0) << endl; return 0; }

水数据 (1/1)

点个赞以后遇到的题全会！！！

1. AI 的 main 有东西读（我偏偏没有） 2. AI 的函数写在 main 前面（我偏偏写后面） 3. AI 的方向数组 dx[], dy[] 是变量（我偏偏写常量）

我已从八月3日（集训营期间）肝至22日，肝！想一起肝的私 想肝时空双修的，麻油头绪，所以只能肝简单粗暴的全勤王了TUT

这道题只能选5 也就是E

ing ing ing 我还没分[]

我6年级都知道(并非恶意)

目测相当简单，只需要建一个list[10]记录每个数字出现次数然后按照出现次数从9往0输出，如果只有0就只输出一个0

咕咕嘎嘎

一道送分题 ？？？