CSP-J基础之数学基础 初等数论 一篇搞懂(一)

2024-09-08 13:28

本文主要是介绍CSP-J基础之数学基础 初等数论 一篇搞懂(一),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 声明
  • 初等数论是什么
  • 初等数论历史
      • 1. **古代时期**
      • 2. **中世纪时期**
      • 3. **文艺复兴与近代**
      • 4. **现代时期**
  • 整数的整除性
    • 约数
    • 什么样的整数除什么样的整数才能得到整数?
      • 条件:
      • 举例说明:
      • 一般化:
    • 判断两个数能否被整除
  • 因数与倍数
  • 质数与复合数
  • 使用开根号法判定质数
  • 哥德巴赫猜想
  • 最大公因数与辗转相除法
      • 计算最大公因数的常用方法:
      • 举几个例子:
        • 例子 1: 计算 12 和 18 的最大公因数
        • 例子 2: 计算 56 和 98 的最大公因数
        • 例子 3: 计算 25 和 40 的最大公因数
    • 编程使用辗转相除法
  • 最小公倍数与求解方法
      • 求解方法:
      • 例子:
      • C语言函数实现:
      • 解释:
      • 示例运行:
  • 总结


前言

在编程竞赛中,数学基础是许多算法和问题求解的核心,尤其是在中国计算机学会(CSP-J)竞赛中,初等数论常常是考察的重点。初等数论研究整数的基本性质及其应用,涵盖了如最大公因数、最小公倍数、质数、同余理论等基本概念和方法。掌握这些内容不仅有助于解答数论相关题目,还能为后续学习复杂的算法打下坚实的基础。

在本文中,我们将深入探讨CSP-J中常见的初等数论知识,从整数的基本运算到辗转相除法、最小公倍数、质数判定、素数筛等经典算法,帮助你快速掌握这些关键数学概念及其应用场景。


声明

此课程是针对全国青少年信息学奥林匹克竞赛而创建的,针对人群有小学,初中,高中,所以各位大学生们嘴下留情!

初等数论是什么

初等数论是研究数的规律,特别是整数性质的数学分支。它是数论的一个最古老的分支。

初等数论历史

初等数学是数学的基础部分,涵盖了算术、代数、几何和初步的三角学等内容。其发展历史可以追溯到几千年前,伴随着人类文明的演进,逐渐形成了如今的体系。以下是初等数学发展的一些重要阶段:

1. 古代时期

  • 古埃及和巴比伦(约公元前3000年 - 公元前300年):最早的数学记录来自古埃及和巴比伦。这些文明使用数学进行日常事务,如土地测量、建筑工程、农业和天文计算。巴比伦人使用了60进制系统,这在时间和角度的测量中至今仍然使用。
  • 古希腊(公元前600年 - 公元300年):古希腊数学家,如毕达哥拉斯、欧几里得和阿基米德,为数学奠定了理论基础。欧几里得的《几何原本》系统地整理了几何学,成为几何学教学的标准。

2. 中世纪时期

  • 印度和伊斯兰数学(公元500年 - 公元1500年):印度数学家引入了“零”的概念,并发展了十进制记数法和代数。9世纪的波斯数学家花拉子米的著作《代数学》不仅推广了代数的应用,还奠定了现代代数的基础。伊斯兰数学家通过翻译希腊和印度的数学著作,对欧洲数学发展产生了重要影响。
  • 中国古代数学:在中国,《九章算术》(约公元前2世纪)系统性地介绍了分数、比例、面积和体积计算等内容,并提出了“盈不足”方法(类似于代数解方程)。《周髀算经》等经典数学著作也推动了中国数学的发展。

3. 文艺复兴与近代

  • 欧洲文艺复兴(公元15世纪 - 17世纪):随着古希腊与阿拉伯数学著作的重新发现,欧洲开始了数学的复兴。意大利数学家如斐波那契引入了阿拉伯数字,并推广了代数的应用。笛卡尔的解析几何学和牛顿、莱布尼兹的微积分理论的创立标志着近代数学的诞生,极大扩展了初等数学的范畴。

4. 现代时期

  • 19世纪 - 20世纪:随着数学领域的进一步分化和专业化,初等数学逐渐在教育体系中独立为一门基础学科。代数、几何和三角学被系统化地整理为中小学的基础课程,而数学教学的形式和内容也得到了标准化。现代初等数学仍然是今天数学教育的重要部分,并且不断通过新的技术和教育理论得以创新。

整数的整除性

约数

约数是一个整数能够整除另一个整数的数,通俗地说,就是“能够把另一个数分成整数份的数”。

比如说:

  • 6 的约数是什么?能够把 6 分成整数份的数有 1、2、3 和 6。因为 6 可以被这些数整除,没有余数,所以它们是 6 的约数。具体来说:
    • 6 ÷ 1 = 6
    • 6 ÷ 2 = 3
    • 6 ÷ 3 = 2
    • 6 ÷ 6 = 1

总结一下:如果你能用某个整数去除另一个整数,而且结果是整数(没有小数或余数),那么前面的那个数就是后面那个数的约数。

什么样的整数除什么样的整数才能得到整数?

对于两个整数 ( a ) 和 ( b ) 来说,如果它们的除法结果是整数,即 ( a \div b ) 得到整数,那么这意味着 ( b ) 是 ( a ) 的约数,或者说 ( a ) 能被 ( b ) 整除。可以用数学语言来描述:

条件:

设 ( a ) 和 ( b ) 是两个整数,( a \div b ) 的结果是整数的条件是:
在这里插入图片描述

其中 ( k ) 是一个整数,表示 ( b ) 可以整除 ( a )。这等价于说 ( b ) 是 ( a ) 的约数,或者说 ( a ) 是 ( b ) 的倍数。

举例说明:

1.在这里插入图片描述
,因为 2 是 10 的约数,5 是整数。
2.在这里插入图片描述
,因为 3 是 15 的约数,5 是整数。
3.在这里插入图片描述
,因为 4 不是 14 的约数,结果不是整数。

一般化:

  • 如果 b整除a,即 b整除a(余数为 0),那么 b整除a 的结果是整数。
  • 如果 a/b 的结果是整数,意味着 a是b的倍数。

因此,只有当一个整数是另一个整数的倍数时,它们的除法结果才是整数。

总结:

  1. 当两个数整除时,如果没有余数,他们相除就是得到整数
  2. 如果一个数是一个整数是另一个整数的倍数时,它们的除法结果也是整数a = b * k

判断两个数能否被整除

bool candiv(int a, int b)
{return (a % b) == 0;
}

因数与倍数

定义1:设a,b是整数, b≠0. 如果有一个整数c,它使得 a=bc, 则a叫做b的倍数,b叫做a的因数。我们有时说,b能整除a 或a能被b整除;

12 = 3 x 4
12 是 3 的倍数,3 是 12 的因数。3能整除12,或12能被3整除

如果b能整除a, 我们可以用 b|a这个符号来表示。如:

以下是几个例子,展示了整除关系及符号表示:

  1. ( 3 | 6 ),因为 3 能整除 6。
  2. ( 5 | 15 ),因为 5 能整除 15。
  3. ( 4 | 12 ),因为 4 能整除 12。
  4. ( 7 | 21 ),因为 7 能整除 21。
  5. ( 9 | 18 ),因为 9 能整除 18。

在每个例子中,左侧的数(如 3, 5, 4, 7, 9)是右侧数的因数。

质数与复合数

引理1:设a,b是两个整数, b≠0. 则一定有并且只有两个整数q,r, 可使以下表达式成立:
在这里插入图片描述
在这里插入图片描述

定义2:一个大于1的正整数,只能被1和它本身整除,不能被其它正整除整除,这样的正整数叫做素数(也叫做质数)。
在这里插入图片描述
定义3:一个正整数除了能被1和它本身整除以外,还能被另外的正整数整除,这样的正整数叫做复合数(也叫做合数)。

在这里插入图片描述
由素数和复合数的定义,可知, 全体正整数可分为三类:
(1) 1这个数
(2)全体素数(质数)
(3)全体复合数(合数)

定义4:如果一个正整数a由一个因数b, 而b又是素数,则b就叫做a的素因数(质因数)。例如,12 = 3 × 4,3是素数,而4不是素数,所以3是12的素因数(质因数)。而4不是12的素因数。

引理1:如果a是一个大于1的整数,则a的大于1的最小因数一定是素数。(可以分素数和合数讨论证明)
这个引理说明了:任何大于1的整数都至少有一个素因数。

在这里插入图片描述
引理2:如果a是一个大于1的整数,而所有≤ 根号a 的素数都除不尽a, 则a是素数。
引理2的意思可以用更通俗的语言表述为:

如果 ( a ) 是一个大于 1 的整数,并且所有小于等于 ( \sqrt{a} ) 的素数都不能整除 ( a ),那么 ( a ) 一定是一个素数。

换句话说,要判断一个数 ( a ) 是否是素数,只需要检查比 ( \sqrt{a} ) 小的素数。如果这些素数都不能整除 ( a ),那么 ( a ) 就是素数。

举例:
比如,假设 ( a = 29 )。我们只需要检查 ( \sqrt{29} \approx 5.39 ) 以下的素数,即 2、3、5:

  • 29 除以 2,得不到整数;
  • 29 除以 3,得不到整数;
  • 29 除以 5,得不到整数。

因此,29 是素数,因为这些素数都无法整除它。

这个引理提供了一个有效的素数判定方法,避免了对所有小于 ( a ) 的数进行检查。

使用开根号法判定质数

bool isPrime(int n) {if (n == 0 || n == 1) return false;for (int i = 2; i <= sqrt(n); i++) {if (n % i == 0) {return false;}}return true;
}

我们通过引言二可以得到上面的代码。
有一个问题,为什么i是2sqrt(n)**而不是**2sqrt(n)中间的素数呢?
这个代码不需要标明 i 是素数的原因是:

如果一个数 ( n ) 能被某个合数(非素数)整除,那么它也一定能被这个合数的因数整除。换句话说,只要检查从 2 到 ( \sqrt{n} ) 之间的所有整数是否能整除 ( n ),就足够判断 ( n ) 是否是素数。

具体原因可以通过以下解释来理解:

  1. 合数的因数分解
    假设 ( n ) 是一个合数,那么它可以写成两个数的乘积 ( n = a \times b ),其中 ( a ) 和 ( b ) 都大于 1。假设 ( a \leq b ),那么必然有 ( a \leq \sqrt{n} )。因此,只要我们检查 ( \sqrt{n} ) 以内的所有整数,肯定可以找到 ( n ) 的一个因数 ( a )(如果存在的话)。

  2. 不需要单独检查素数
    假如 ( i ) 是合数,比如 ( i = 6 ),如果 ( n ) 能被 6 整除,说明 ( n ) 也能被 2 或 3 整除(因为 6 是 2 和 3 的乘积)。而在遍历时,程序已经检查了 2 和 3,没必要再单独检查 6 这个合数。换句话说,合数的因数会在之前的循环中通过它们的较小素数因子被检测到。

因此,通过遍历从 2 到 ( \sqrt{n} ) 之间的所有整数,我们已经能有效地判断 ( n ) 是否是素数,而不需要特别标明 ( i ) 是否是素数。

哥德巴赫猜想

哥德巴赫猜想:凡是大于2的偶数都是两个奇素数之和!如:

6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5,
12 = 5 + 7, 14 = 7 + 7, 16 = 3 + 13,
18 = 5 + 13, 20 = 7 + 13, 22 = 3 + 19

哥德巴赫猜想并未完全验证,只是在一个特定范围内的数有效果

最大公因数与辗转相除法

最大公因数(Greatest Common Divisor, GCD),又称为最大公约数,是指两个或多个整数的共有因数中最大的那个数。换句话说,最大公因数是能够整除这些整数的最大的正整数。

计算最大公因数的常用方法:

  1. 列出所有因数法:分别列出每个数的所有因数,然后找出它们的公共因数中的最大者。
  2. 欧几里得算法(辗转相除法):基于以下定理:对于两个整数 (a) 和 (b),它们的最大公因数等于 (b) 和 (a % b) 的最大公因数,反复进行这个过程直到余数为 0,最后的非零余数即为最大公因数。

在这里插入图片描述

举几个例子:

例子 1: 计算 12 和 18 的最大公因数
  1. 列出因数法

    • 12 的因数:1, 2, 3, 4, 6, 12
    • 18 的因数:1, 2, 3, 6, 9, 18
    • 公共因数:1, 2, 3, 6
    • 最大的公共因数是 6,因此 ( \text{GCD}(12, 18) = 6 )。
  2. 欧几里得算法
    在这里插入图片描述

例子 2: 计算 56 和 98 的最大公因数
  1. 列出因数法

    • 56 的因数:1, 2, 4, 7, 8, 14, 28, 56
    • 98 的因数:1, 2, 7, 14, 49, 98
    • 公共因数:1, 2, 7, 14
    • 最大的公共因数是 14,因此 ( \text{GCD}(56, 98) = 14 )。
  2. 欧几里得算法
    在这里插入图片描述

例子 3: 计算 25 和 40 的最大公因数
  1. 列出因数法

    • 25 的因数:1, 5, 25
    • 40 的因数:1, 2, 4, 5, 8, 10, 20, 40
    • 公共因数:1, 5
    • 最大的公共因数是 5,因此 ( \text{GCD}(25, 40) = 5 )。
  2. 欧几里得算法
    在这里插入图片描述

编程使用辗转相除法

根据定义,我们可以写出下面代码

int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}

如果这里用递归会更加简洁

最小公倍数与求解方法

最小公倍数(Least Common Multiple, LCM)是指能够同时被两个或多个整数整除的最小正整数。换句话说,最小公倍数是这些整数的公倍数中最小的一个。

求解方法:

  1. 质因数分解法:将每个数分解为质因数,然后取每个质因数的最高次幂相乘。

  2. 最大公因数法:利用两个数的最大公因数(GCD)与最小公倍数的关系:
    在这里插入图片描述

    这里 ( GCD(a, b) ) 是两个数的最大公因数。

例子:

  • LCM(12, 18)
    1. 求 GCD(12, 18) = 6(可以通过辗转相除法求得)。
    2. 计算 LCM(12, 18) = ( )。
      在这里插入图片描述

C语言函数实现:

我们可以结合先求最大公因数(GCD),然后通过公式计算最小公倍数(LCM)。以下是一个完整的 C 语言实现:

#include <stdio.h>// 计算最大公因数(GCD)的函数,使用辗转相除法
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}// 计算最小公倍数(LCM)的函数
int lcm(int a, int b) {return (a * b) / gcd(a, b);  // 利用LCM与GCD的关系
}int main() {int num1, num2;printf("请输入两个整数:");scanf("%d %d", &num1, &num2);printf("最小公倍数是:%d\n", lcm(num1, num2));return 0;
}

解释:

  1. 函数 gcd:使用辗转相除法计算最大公因数。
  2. 函数 lcm:利用 ( \text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)} ) 公式计算最小公倍数。
  3. main 函数:接受用户输入两个整数,并输出它们的最小公倍数。

示例运行:

请输入两个整数:12 18
最小公倍数是:36

这个程序通过先计算最大公因数,再利用公式求解最小公倍数。


总结

通过本文的学习,你应该对初等数论的基础知识有了全面的理解。从最大公因数、最小公倍数的求解方法到质数的判定,我们不仅分析了这些概念的数学原理,还提供了高效的算法实现。初等数论不仅是竞赛中的重要模块,也是许多算法的基础。掌握这些数学技巧后,你将能够应对更多复杂的数论问题,为解决更高级别的编程挑战奠定基础。

希望本文能够为你的CSP-J备考提供帮助,并激发你对数论的进一步兴趣与探索。

这篇关于CSP-J基础之数学基础 初等数论 一篇搞懂(一)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1148239

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具,采用无代理架构(agentless),基于 SSH 连接进行管理,具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用,旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念

数论ZOJ 2562

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。 分析:反素数定义:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close