当前位置： 首页 > news >正文

第二十天：数论度量

news 2025/8/10 7:26:06

每日一道C++题：数论度量

一、 最大公约数

方法一：欧几里得算法（辗转相除法）

原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

#include <iostream>
using namespace std;int gcd(int a, int b) {while (b!= 0) {int temp = b;b = a % b;a = temp;}return a;
}int main() {int m, n;cin >> m >> n;cout << gcd(m, n) << endl;return 0;
}

gcd 函数：
欧几里得算法（又称辗转相除法）是计算两个整数最大公约数（GCD）的高效算法。其基本原理基于以下数学定理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

算法实现步骤如下：

  1. 定义一个函数 gcd(a, b)：

    • 初始化 while 循环，条件为 b != 0
    • 在循环体内：
      a. 将 b 的值暂存到临时变量 temp 中
      b. 计算 a 除以 b 的余数，并将结果赋给 b
      c. 将 temp（原 b 值）赋给 a
    • 循环终止后，返回 a 的值即为最大公约数

  2. 主函数 main 的实现：

    • 从标准输入读取两个正整数 m 和 n（建议添加输入验证确保为正整数）
    • 调用 gcd(m, n) 函数计算最大公约数
    • 输出计算结果

示例演示：
假设输入 m=48，n=18：
第一次迭代：temp=18, b=48%18=12, a=18
第二次迭代：temp=12, b=18%12=6, a=12
第三次迭代：temp=6, b=12%6=0, a=6
循环结束，返回GCD=6

应用场景：

  • 分数化简（分子分母约分）
  • 密码学中的模运算
  • 解决线性同余方程
  • 计算最小公倍数（LCM = a*b/GCD）

注意事项：

  1. 算法要求输入必须为正整数
  2. 当其中一个数为0时，另一个数即为最大公约数
  3. 算法的时间复杂度为O(log min(a,b))，效率很高

方法二：更相减损术

原理：两个正整数 a 和 b（a > b），它们的最大公约数等于 a - b 和 b 的最大公约数，不断重复这个过程，直到 a = b，此时 a（或 b）就是最大公约数。

#include <iostream>
using namespace std;int gcd(int a, int b) {while (a!= b) {if (a > b) {a = a - b;} else {b = b - a;}}return a;
}int main() {int m, n;cin >> m >> n;cout << gcd(m, n) << endl;return 0;
}

gcd 函数（欧几里得算法的减法实现）：
该函数通过反复相减的方式计算两个数的最大公约数。具体执行步骤如下：

  1. 使用 while 循环持续比较 a 和 b 的值，循环条件为 a != b
  2. 在循环体内：
    • 当 a > b 时，执行 a = a - b（将较大的数减去较小的数）
    • 当 b > a 时，执行 b = b - a（将较大的数减去较小的数）
  3. 当 a 和 b 相等时，循环终止，此时 a 或 b 的值即为两数的最大公约数
  4. 返回最终的 a 值

例如计算 gcd(48, 18)：
第一次循环：48 > 18 → 48-18=30
第二次循环：30 > 18 → 30-18=12
第三次循环：18 > 12 → 18-12=6
第四次循环：12 > 6 → 12-6=6
此时 a == b == 6，循环结束，返回 6

main 函数：

  1. 声明整型变量 m 和 n 用于存储用户输入
  2. 使用 scanf 函数从标准输入读取两个整数，分别赋给 m 和 n
  3. 调用 gcd(m, n) 函数计算最大公约数
  4. 使用 printf 函数输出计算结果
  5. 返回 0 表示程序正常结束

注意事项：

  • 输入的两个数应为正整数
  • 当输入数字较大时，减法实现的效率可能较低
  • 该实现方式直观展示了欧几里得算法的基本原理。

欧几里得算法在大多数情况下效率更高，因为它通过取余操作减少了运算次数。而更相减损术相对来说运算次数可能较多，但理解起来更直观。

二、 最小公倍数

最小公倍数(LCM)是数学中的重要概念，指能同时被两个数a和b整除的最小正整数。计算时可以通过它与最大公约数(GCD)的关联关系来简化运算过程。

具体而言，对于任意两个正整数a和b，它们的最小公倍数与最大公约数之间存在以下数学关系：
LCM(a, b) × GCD(a, b) = a × b

这个关系式非常有用，因为在计算时，我们可以先求出两个数的最大公约数，然后利用上述公式快速得到最小公倍数。例如，计算12和18的最小公倍数：

  1. 先求GCD(12,18)=6
  2. 根据公式：LCM(12,18) = (12×18)/6 = 36
#include <iostream>
using namespace std;// 欧几里得算法求最大公约数
int gcd(int a, int b) {while (b!= 0) {int temp = b;b = a % b;a = temp;}return a;
}// 求最小公倍数
int lcm(int a, int b) {return a * b / gcd(a, b);
}int main() {int num1, num2;cout << "请输入两个整数: ";cin >> num1 >> num2;int resultLcm = lcm(num1, num2);cout << "这两个数的最小公倍数是: " << resultLcm << endl;return 0;
}

三、 所有公因数

要找出两个数的所有公因数，可以按照以下步骤进行操作：

  1. 首先计算这两个数的最大公约数（GCD）。常用的方法包括：

    • 辗转相除法（欧几里得算法）：通过反复用较大数除以较小数，直到余数为0，最后的除数就是GCD
    • 质因数分解法：将两个数分别分解质因数，然后取所有公共质因数的最小指数的乘积

  2. 得到GCD后，找出GCD的所有因数。可以采用以下方法：

    • 从1到GCD进行遍历，对每个数i检查GCD%i==0
    • 或者更高效的方法是：遍历1到√GCD，每当找到一个因数i时，同时记录对应的因数GCD/i

  3. 这些因数就是原始两个数的所有公因数。

示例：
求36和48的公因数：

  • 先计算GCD(36,48)=12
  • 然后找出12的所有因数：1,2,3,4,6,12
  • 所以36和48的公因数为{1,2,3,4,6,12}

应用场景：

  • 分数约分时需要知道分子分母的所有公因数
  • 在密码学中，某些算法需要计算两个数的公因数
  • 在图形学中，计算图像尺寸的比例时可能需要用到公因数

这种方法的时间复杂度主要取决于计算GCD的算法效率，使用欧几里得算法的时间复杂度是O(log(min(a,b)))。

#include <iostream>
#include <vector>
using namespace std;// 欧几里得算法求最大公约数
int gcd(int a, int b) {while (b!= 0) {int temp = b;b = a % b;a = temp;}return a;
}// 找出一个数的所有因数
vector<int> findFactors(int num) {vector<int> factors;for (int i = 1; i <= num; i++) {if (num % i == 0) {factors.push_back(i);}}return factors;
}int main() {int num1, num2;cout << "请输入两个整数: ";cin >> num1 >> num2;int gcdValue = gcd(num1, num2);vector<int> commonFactors = findFactors(gcdValue);cout << "这两个数的所有公因数是: ";for (int factor : commonFactors) {cout << factor << " ";}cout << endl;return 0;
}

四、区间内素数个数

要判断一个数是否为素数，可以采用如下的详细步骤：

  1. 特殊情况处理：

    • 如果数字小于2，直接判定为非素数
    • 如果数字等于2，判定为素数（2是最小的素数）
    • 如果数字是大于2的偶数，直接判定为非素数

  2. 常规判断方法：

    • 计算该数的平方根，记为 (\sqrt{n})，并取整数部分
    • 用3到(\sqrt{n})之间的所有奇数作为除数，依次进行试除
    • 如果发现能被其中任何一个数整除，则立即判定为非素数
    • 如果遍历完所有可能的除数都没有整除情况，则判定为素数

  3. 区间素数统计：

    • 对于给定的区间 ([m, n])，首先确保m ≥ 2
    • 逐个检查区间内的每个整数
    • 对每个整数应用上述素数判断方法
    • 维护一个计数器，每当发现一个素数时就增加计数

  4. 优化技巧：

    • 可以预先计算并存储较小的素数列表，用于加快大数的判断
    • 使用埃拉托斯特尼筛法可以更高效地统计区间内的素数
    • 对于连续的区间统计，可以记录之前的判断结果避免重复计算

  5. 实际应用示例：

    • 计算100到200之间的素数个数：
      1. 从101开始检查（100是偶数直接跳过）
      2. 检查101时，试除3,5,7（因为√101≈10）
      3. 发现101不能被这些数整除，判定为素数
      4. 如此继续直到200，最后统计总数

  6. 注意事项：

    • 对于大数区间，算法效率可能较低，需要考虑更优化的算法
    • 在编程实现时，要注意整数溢出的问题
    • 可以并行处理以加快统计速度，特别是在大数据量的情况下。
#include <iostream>
using namespace std;// 判断一个数是否为素数
bool isPrime(int num) {if (num <= 1) return false;for (int i = 2; i * i <= num; i++) {if (num % i == 0) {return false;}}return true;
}// 统计区间内素数个数
int countPrimesInRange(int m, int n) {int count = 0;for (int i = m; i <= n; i++) {if (isPrime(i)) {count++;}}return count;
}int main() {int m, n;cout << "请输入区间的起始值和结束值: ";cin >> m >> n;int primeCount = countPrimesInRange(m, n);cout << "区间 [" << m << ", " << n << "] 内的素数个数是: " << primeCount << endl;return 0;
}
http://www.lryc.cn/news/615069.html

相关文章：

  • 【面试场景题】通过LinkedHashMap来实现LRU与LFU
  • C++隐式转换的魔法与陷阱：explicit关键字的救赎
  • 软件工程总体设计：从抽象到具体的系统构建之道
  • Python基础教程（六）条件判断：引爆思维Python条件判断的九层境界
  • 轻量化阅读应用实践：21MB无广告电子书阅读器测评
  • MySQL(188)如何使用MySQL的慢查询工具？
  • Spring Boot 2 集成 Redis 集群详解
  • 聊聊经常用的微服务
  • MBR分区nvme固态硬盘安装win7--非UEFI启动和GPT分区
  • day30-HTTP
  • 大语言模型提示工程与应用：LLMs文本生成与数据标注实践
  • 在Docker中下载RabbitMQ(详细讲解参数）
  • docker基础前置
  • STM32H503不同GPIO速度配置（HAL库）对应的最高速度
  • 【linux基础】Linux 文本处理核心命令指南
  • 麒麟系统 安装vlc
  • NumPy性能飞跃秘籍：向量化计算如何提升400倍运算效率？
  • Pytorch模型复现笔记-FPN特征金字塔讲解+架构搭建（可直接copy运行）+冒烟测试
  • 工业场景反光衣识别准确率↑32%：陌讯多模态融合算法实战解析
  • 【阿里巴巴大数据实践之路学习记录】第十章-维度设计
  • 强化学习-MATLAB
  • bms部分
  • Day38 Dataset和Dataloader类
  • 强光干扰下误报率↓82%！陌讯多模态算法在睡岗检测的落地优化
  • 分享一个基于Spark的眼科疾病临床数据可视化分析与应用研究Hadoop基于Vue和Echarts的眼科疾病统计数据交互式可视化系统的设计与实现
  • JS逆向实战案例之----【通姆】252个webpack模块自吐
  • ComfyUI——舒服地让大模型为我所用
  • QT第二讲-信号和槽
  • Openlayers基础教程|从前端框架到GIS开发系列课程（19）地图控件和矢量图形绘制
  • 【C++详解】AVL树深度剖析与模拟实现（单旋、双旋、平衡因⼦更新、平衡检测）