数论idx

典型问题

学什么

数量模式

• 什么是“数量模式”
  • 一个数可以表示、体现大小，是默认“单位=个”的前提下
    • 比如，5>3，这里5是5个，3是3个，默认这个含义
    • 若3表示3万，大小关系就不一样了
  • 更普遍的大小，是用“数·量”来表达
    • 比如：1公斤、3小时、一条鱼、一筐鱼、一斤鱼…

四舍五入

• 【底层逻辑】如何理解“四舍五入”
  • 目的
    • 牺牲精度，换表达的简化
    • 精度，取决于最后一位的“单位”
      • 四舍五入到“万”，最后一位是“万”
      • 四舍五入到“2位小数”，最后一位是“百分之一”
      • 四舍五入到“万，保留2位小数”，最后一位是“百”
    • 精度，体现为“有效数字的长度”
  • 原则
    • 最接近
      • 比如74四舍五入到十位=7（十），相差74-70=4
      • 若，74四舍五入到十位=8（十），则相差80-74=6，不好
      • 70是与74最接近的整十数
• “四舍五入”的几个不同体现
• “四舍五入”的类似处理
• “四舍五入”与单位换算的关联
  • 两者，都是基于“数量模型”

同余定理

• 一句话
  • 计算的余数=余数的计算

数论

整除

整除判断法则

规则一览

逻辑图谱

整除判断法则，核心思维是：A=B+C，分理处（绝大部分）不需要判断的部分，只分析剩下的小尾巴。但这个方法的实现，方式各异，相近或相远。若再考虑组合判断，则形成了一个判断方法的拓扑。有利于系统的理解判断法则，以及养成结构化分析习惯、学习习惯。

指向原始笔记的链接

详细内容，参考：整除判断法则及逻辑图谱

扎实理解整除的应用练习

题目参考

第一个2016在哪里？-约数分解应用2024.03.17-小帅

在一个三角形数阵中，如何定位2016位置？一方面需要因数分解基础知识，如何分解和最小的认知与方法，另一方面还需要归纳、总结等基础能力。特别的，不是专题练习时，需要自己想到做因数分解。这要求我们不仅知道知识，还知道其价值。

指向原始笔记的链接

数论/公约数公倍数

• 参考 《高思课本·五上·15讲·公约数公倍数进阶》

GCD-LCM的关键逻辑

• 基础关系
  • $A\times B=(A,B)\times [A,B]$
  • 注1，这是最重要、最核心的一个约束关系
  • 注2，仅记住不够——不能灵活应用，需要理解“分析思路”
  • 注3，两个数的关系，有局限性；三个或以上数字的公约数、公倍数关系，没有体现
• 背后的分析思路
  • 定义：$A=GCD\times a；B=GCD\times b$
  • 易得：$LCM=GCD\times a\times b$
  • 注1：这是理解$A\times B=(A,B)\times [A,B]$的好思路
  • 注2：实际中，这个理解思路，常常比结论本身更好用
• 容易忽略的约束
  • 在$A=GCD\times a；B=GCD\times b$中，a和b互质
    • 这是GCD中“G”的隐含要求
    • 这一点，容易被忽略
• 参考（2024课堂）

GCD-LCM与容斥图

• 数论/公约数公倍数/容斥关系
• 知识交叉
  • 同时加深对两块知识的理解
  • 容易触及更底层的逻辑
• 两个数的容斥关系
• 三个数的容斥关系
• 多个数的容斥关系
  • 不！好！弄！

公倍数的逻辑转化

• 最初定义
  • 倍数：如果a÷b=整数，那么a是b的倍数
  • 公倍数：
    • a的倍数a、2a、3a、4a…
    • b的倍数b、2b、3b、4b…
    • 以上2个数列中，共同的数字，称为a、b的公倍数
• 最初定义，简洁、清晰；但不意味着逻辑好用
• 逻辑转化——换个等价的定义方式
  • x的质因数分解：$x=a_1^{n_1}\times a_2^{n_2}\times a_3^{n_3}\times ...$
  • y的质因数分解：$y=a_1^{m_1}\times a_2^{m_2}\times a_3^{m_3}\times ...$
  • z的质因数分解：$z=a_1^{k_1}\times a_2^{k_2}\times a_3^{k_3}\times ...$
  • 如果指数满足以下条件，那么y是x的倍数$m_1\ge n_1，m_2\ge n_2，m_3\ge n_3，...$
  • 如果指数满足以下条件，那么z是x、y的倍数$k_1\ge max(n_1,m_1)，k_2\ge max(n_2,m_2)，k_3\ge max(n_3,m_3)...$
• 以上表达，看起来挺吓人，但实际上很简单

多个数的LCM

• 并不容易
  • 短除法
    • 求2个数GCD、LCM可以
    • 3个或以上数，会碰到困难
  • 质因数分解
    • 有机会解决问题，但需要一点思考
• 方法1，短除法，适用2-3个数
• 方法2，质因数分解，适用2、3、4、5…个数
  • [3696、5445、702]=？
  • 解：
    • $3696=2^4\times 3\times 7\times 11$
    • $5445=3^2\times 5\times 11^2$
    • $702=2\times 3^3\times 13$
    • $[3696,5445,702]=2^4\times 3^3\times 5\times 7\times 11^2\times 13=23783760$
    • 这里
      1. 底，$2^{()}、3^{()}、5^{()}、7^{()}、11^{()}、13^{()}$，应有尽有
      2. 指数，$({)}^4、({)}^3、({)}^1、({)}^1、({)}^2、({)}^1$，取最大的
  • 此方法，适用3个以上求公倍数
  • 此方法，参考 【公倍数逻辑转化】

三个数的公倍数，面临的问题

GCD-LCM反求数值，即“互质枚举”“分组组合”

• 参考问题 〚高思课本.5A.15.e1〛公约数公倍数反求，互质枚举
• 这个问题需要两个能力
  • 关键逻辑
  • 互质枚举
• 互质枚举
  • 如果a×b=660，且a、b互质（除1之外没有其他公约数）
  • 列出所有可能的情况：
  • $660=2^2\times 3\times 5\times 11$
    • （$1$，$2^2\times 3\times 5\times 11$）
    • （$2^2$，$3\times 5\times 11$）
    • （$3$，$2^2\times 5\times 11$）
    • （$5$，$2^2\times 3\times 11$）
    • （$11$，$2^2\times 3\times 5$）
    • （$2^2\times 3$，$5\times 11$）
    • （$2^2\times 5$，$3\times 11$）
    • （$2^2\times 11$，$3\times 5$）
• 互质枚举，一般结论
  • 如果a×b=$p_1^{()}{p}_2^{()}{p}_3^{()}...p_n^{()}$，且a、b互质（除1之外没有其他公约数）
  • 则a、b所有可能的情况有多少种？
  • 答
    • $情况个数=2^{n-1}$
• 示例
  1. 若两个数，最大公约数是18，最小公倍数是1080，那么这两个数有哪几组？
  2. 若两个数，最大公约数是2，最小公倍数是1320，那么这两个数有几组？
  3. 若两个数，最大公约数是2，最小公倍数是27720，那么这两个数有几组？
  4. 若两个数，最大公约数是2，最小公倍数是60060，那么这两个数有几组？
  5. 如果仅回答个数，是否有简单清晰的计算方法？
  • 解答：
    1. $1080÷18=60=4\times 3\times 5$
       • 个数：$2^{3-1}=4$
       • 枚举：（1，4×3×5）（4，3×5）（3，4×5）（5，4×3）
    2. $1320÷2=660=2^2\times 3\times 5\times 11$
       • 个数：$2^{4-1}=8$
       • 枚举：（1，2^2×3×5×11）（2^2，其他）（3，其他）（5，其他）（11，其他）$$（2^2×3，其他）、（2^2×5，其他）、（2^2×11，其他）
    3. $27720÷2=13860=4\ast 9\ast 5\ast 7\ast 11$
       • 个数：$2^{5-1}=16$
       • 枚举：略
    4. $60060÷2=2\ast 3\ast 5\ast 7\ast 11\ast 13$
       • 个数：$2^{6-1}=16$
       • 枚举： C_5^0=1个：（1，2^2×3×5×11）$$$C_5^1=5个：（2，其他）、（3，其他）、（5，其他）、（7，其他）、（11，其他）$$（2^2×3，其他）、（2^2×5，其他）、（2^2×11，其他）

GCD-LCM 更多性质