【No.20】蓝桥杯简单数论下|寻找整数|素数的判断|笨小猴|最大最小公倍数|素数筛|埃氏筛|欧氏线性筛|质数|分解质因子(C++)

2024-03-27 11:36
文章标签 简单 c++ 判断 最小 质数 最大 蓝桥 线性 数论 整数 分解 素数 因子 寻找 公倍数 no.20 埃氏 欧氏 笨小猴

本文主要是介绍【No.20】蓝桥杯简单数论下|寻找整数|素数的判断|笨小猴|最大最小公倍数|素数筛|埃氏筛|欧氏线性筛|质数|分解质因子(C++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

寻找整数

【题目描述】
有一个不超过 1 0 1 7 10^17 1017的正整数n，知道这个数除以2至49后的余数如下表所示，求这个正整数最小是多少
![[Pasted image 20240326202941.png]]

解法一：模拟

暴力法：一个个检验 1 … 1 0 17 1\dots 10^{17} 1…1017的每个数
由于这个数n最大可能是 1 0 17 10^{17} 1017，验证的时间太长

解法二：LCM

从表格的第一个数2开始，逐个增加后面的数，找满足条件的n

  1. 满足第一个条件，除以2余1的数有：3，5，7，9…此时步长k=2
  2. 继续满足第二个条件，除以3余2的数，只能从上一步骤的3，5，7，9…中找，有5，11，17…此时步长k=6
    为什么k=6
    因为LCM：k=(2, 3)=6

证明:
设 n 1 n_{1} n1​和 n 2 n_{2} n2​满足
n 1 = 2 a 1 + 1 = 3 b 1 + 2 n_{1}= 2a_{1}+1 = 3b_{1}+2 n1​=2a1​+1=3b1​+2
n 2 = 2 a 2 + 1 = 3 b 2 + 2 n_{2}=2a_{2}+1= 3b_{2}+2 n2​=2a2​+1=3b2​+2
n 2 n_{2} n2​和 n 1 n_{1} n1​的差 k = n 2 − n 1 = 2 ( a 2 − a 1 ) = 3 ( b 2 − b 1 ) k=n_{2}-n_{1}=2(a_{2}-a_{1})=3(b_{2}-b_{1}) k=n2​−n1​=2(a2​−a1​)=3(b2​−b1​)
k是2的倍数 ，也是3的倍数，那么k是2和3的最小公倍数，k=lcm(2，3)=6
3. 继续满足第三个条件，除以4余1的数，只能从5，11，17…中找，有5，17，29…此时步长k=lcm(2, 3, 4)=12
4. 继续满足第四个条件…
逐个检查表格，直到满足表格中所有的条件
计算量极小。只需要对表格中的2~49做48次LCM即可

#include <bits/stdc++.h>
using namespace std;
const int N = 50;
int mod[N]=
{0,0,1,2,1,4,5,4,1,2,9,0,5,10,11,14,9,0,11,18,9,11,11,15,17,9,23,20,25,16,29,27,25,11,17,4,29,22,37,23,9,1,11,11,33,29,15,5,41,46};
int main()
{long long ans = 2 + mod[2l;long long k = 2;//从第一个数的步长开始for(int i = 3; i < N; i ++){while(true){if(ans % i == mod[i]){ //ans是满足前i个数的解k=k / __gcd(k，(long long)i)*i;//连续做LCMbreak;}else {ans += k;	//累加新的步长}}}cout<<ans<<endl;return;
}
素数的判断

素数定义：只能被 1 和自己整除的正整数。
注：1 不是素数，最小素数是 2。
判断一个数 n 是不是素数：当n≤10^14时，用试除法；n > 10^14 时，试除法不够用，需要用高级算法，例如 Miller_Rabin 算法。
试除法： 用[2,n-1]内的所有数去试着除 n，如果都不能整除，就是素数。
优化：把[2,n-1]缩小到2到 n \sqrt{ n } n ​。证明：若 n = a x b, 设 a≤ n \sqrt{ n } n ​​ ,则 b≥ \sqrt{ } ​​,如果 a 是 n 的因子，说明 n 不是素数，b 不用再试且 b 一定也是。

#include <iostream>
#include <cmath>bool is_prime(long long n){if(n <= 1)return false; // 1不是素数for(long long i = 2; i <= sqrt(n); i++)if(n % i == 0)return false; // 能整除，不是素数return true; // 全不能整除，是素数
}int main() {long long number = 29; // 例子：要检查是否为素数的数值if (is_prime(number))std::cout << number << " 是素数。" << std::endl;elsestd::cout << number << " 不是素数。" << std::endl;return 0;
}

因为sqrt求出的数不一定是整数，它其实是double的
加一个判断

k = sqrt(n);
if (k * k != n)k += 1;
笨小猴

【题目描述】
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:
假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数
如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky word，这样的单词很可能就是正确的答案。
【输入描述】
输入文件只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。
【输出描述】输出文件共两行，第一行是一个字符串，假设输入的的单词是Lucky word，那么输出“Lucky Word”，否则输出“No Answer”;
第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。

模拟，统计每个字母出现的次数，然后判断

#include <bits/stdc++.h>
using namespace std;
int letter[26] = {0};//统计每个字母的个数，是一个hash表
int is_prime(int n)
{if(n <= 1)return 0;for(int i = 2; i <= sqrt(n); i ++)if(n % i == 0)return 0;return 1;
int main()
{int maxn = -1, minn = 1000;string s;cin >> s;int len = s.length();for(int i = 0; i < len; i ++)letter[s[i]-'a'] ++;for(int i = 0; i < 26; i ++){if(letter[i] == 0)continue;if(letter[i] > maxn)maxn = letter[i];if(letter[i] < minn)minn = letter[i];}if(len == maxn)minn = 0;int ans = is_prime(maxn - minn);if(!ans)cout << "No Answer\n" << 0 << "\n";elsecout << "Lucky Word\n" << maxn - minn << "\n";return 0;
}
最大最小公倍数

【题目描述】
已知一个正整数n，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。
【输入描述】
一个正整数N。
【输出描述】
一个整数表示答案

思路 质数的性质

贪心，从大的数开始选，不过，简单地把N里面最大的三个数相乘，N*(N-1)*(N-2)，并不正确，需要分析多种情况

最小的公倍数是三个数的质因数相乘，如果有几个质因数相同，则比较两数中哪个数的质因数的个数较多。
例如6、7、8的最小公倍数，先分解因子:6=2x3，7=7x1，8=2x2x2，它们的最小公倍数是3x7x2x2x2。

大于1的两个相邻整数互质，它们没有公共的质因数。如果题目是任选二个数，最大的最小公倍数是N*(N-1)

对于连续的三个整数，分两种情况:

  1. N是奇数。
    N、N-1、N-2是奇偶奇，结论是这三个数两两互质，三个数的乘积就是最大的最小公倍数。三个数两两互质，也就是说任意一个质数，只在N、N-1、N-2中出现一次。
    逐个分析质数因子:
    质因数2，只在N-1中出现
    质因数3，如果在N中出现(设N=3a)，就不会在N-1中出现(这要求N-1=3b，无解)，也不会在N-2中出现(这要求N-2=3b，无解)
    推广到任何一个质数k，都只会在N、N-1、N-2中出现一次，所以三个数互质。
  2. N是偶数。
    如果N为偶数，那么N与N-2最大公约数为2，所以我们要找下一个质数，此时需要考虑N与N-3的关系:
    如果N能被3整除，则N-3也能被3整除，此时N与N-3不互质，但是N-1与N-3必然互质(N-1、N-3都为奇数)，所以N-1、N-2、N-3
    如果N不能被3整除，则N-3也不能被3整除，此时N与N-3互质，所以选择N、N-1、N-3
#include <bits/stdc++.h>
using namespace std;
int main()
{long long n, ans;cin >> n;if(n <= 2)ans = n;else if(n % 2)  //n是奇数ans = n * (n - 1) * (n - 2); else   //n是偶数{   if(n % 3)      //n没有因数3ans = n * (n - 1) * (n - 3);  else          //n有因数3ans = (n - 1) * (n - 2) * (n - 3);}cout << ans;return 0;
}
素数筛

素数的筛选：给定 n，求 2~n 内所有的素数。
一个个地判断很慢，所以用“筛子”筛所有的整数，把非素数筛掉，剩下的就是素数。
常用两种筛法：埃氏筛、欧拉筛。
埃氏筛:
初始队列{2、3，4，5，6，7，8，9，10，11，12，13，…，n}
操作步骤：

  1. 输出最小的素数 2，筛掉 2 的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，…}
  2. 输出最小的素数 3，筛掉 3 的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，…}
  3. 输出最小的素数 5，筛掉 5 的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，…}
  4. 继续以上步骤，直到队列为空。
int primes[N], cnt;
bool bprime[N];
void getPrime(int n)
{memset(bprime, false, sizeof(bprime));bprime[0] = true;bprime[1] = true;for(int i = 2; i <= n; i ++){if(!bprime[i]){prime[cnt++] = i;for(LL j = i * 2; j <= n; j += i)bprime[j] = true;}}
}

但是埃氏筛法的缺点：例如 6 会被 3 整除，6 会被 2 整除，会被筛两次，所以我们再给出欧氏线性筛法：

int primes[N], cnt;
bool bPrime[N];
void getPrimes(int n)
{memset(bPrime, false, sizeof(bPrime));for(int i = 2; i <= n; i ++){if(!bPrime[i])primes[cnt++] = i;for(int j = 0; j < cnt && i * primes[j] < n; j ++){bPrime[i * primes[j]] = true;if(i % primes[j] == 0)break;}}
}
质数 lanqiaoOJ 题号 1557

【题目描述】
给定一个正整数 N，请你输出 N 以内（不包含 N）的质数以及质数的个数。
【输入描述】
一个正整数 N，n<1000
【输出描述】
两行，第 1 行包含若干个素数，从小到大输出，用空格分开。
第 2 行一个整数，表示素数个数。
输入：

10

输出：

2 3 5 7 
4

题目为模板题目，实现方式如下，其中：

  • bprime[i]记录数 i 的状态，若 bprime [i]=1，表示它被筛掉，不是素数。
  • 用 primes[]存放素数，prime[0]是第一个素数 2。
  • cnt 是素数个数计数
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int primes[N], cnt;
bool bprime[N]; //true表示被筛掉，不是素数
void getPrimes(int n)  //埃氏筛，计算[2, n]内的素数
{   memset(bprime, false, sizeof(bprime));bprime[0] = true;bprime[1] = true;for(int i = 2; i <= n; i ++){if(!bprime[i]){primes[cnt++] = i;for(int j = i * 2; j <= n; j += i)bprime[j] = true;}}
}int main(){int n;cin >> n;getPrimes(n - 1);for(int i = 0; i < cnt; i ++)  cout << primes[i] << " ";cout << endl;cout << cnt;
}
分解质因子

任何一个正整数 n 都可以唯一地分解为有限个素数的乘积： n = p 1 c 1 p 2 c 2 p 3 c 3 … p m c m n=p_{1}^{c_{1}}p_{2}^{c_{2}}p_{3}^{c_{3}}\dots p_{m}^{c_{m}} n=p1c1​​p2c2​​p3c3​​…pmcm​​​,其中 c i c_{i} ci​都是正整数， p i p_{i} pi​都是素数且从小到大。
分解质因子也可以用试除法。求 n 的质因子：

  1. 求最小质因子p1​。逐个检查从2到 n \sqrt{ n } n ​​ 的所有素数，如果它能整除 n，就是最小质因子。然后连续用 p 1 p_{1} p1​​除 n，目的是去掉 n 中的 p 1 p_{1} p1​​,得到 n 1 n_{1} n1​​。
  2. 再找 n 1 n_{1} n1​​的最小质因子。逐个检查从 p 1 p_{1} p1​​ 到 n 1 \sqrt{ n_{1} } n1​ ​​​ 的所有素数。从 p 1 p_{1} p1​开始试除， 是因为 n 1 n_{1} n1​​没有比 p 1 p_{1} p1​​小的素因子，而且 n 1 n_{1} n1​​的因子也是 n 的因子。
  3. 继续以上步骤，直到找到所有质因子。
    我们直接看一个例题：
    【题目描述】
    求出区间[a,b]中所有整数的质因数分解。
    【输入描述】
    输入一行，包含 2 个整数 a，b。2<=a<=b<=10000
    【输出描述】
    每行输出一个数的分解，形如 k=a1×a2×a3×…，k 从小到大，a 从小到大。
    输入：
3 10

输出：

3=3
4=2×2
5=5
6=2×3
7=7
8=2×2×2
9=3×3
10=2×5​

直接对每个数进行分解，然后打印出它的因数。

#include <bits/stdc++.h>
using namespace std;
int p[20];  //p[]记录因子，p[1]是最小因子。一个int数的质因子最多有10几个
int c[40];  //c[i]记录第i个因子的个数。一个因子的个数最多有30几个
int factor(int n)
{int m = 0;for(int i = 2; i <= sqrt(n); i ++)if(n % i == 0){p[++m] = i, c[m] = 0;while(n % i == 0)         //把n中重复的因子去掉n/=i, c[m]++;}if(n > 1)                           //没有被除尽，是素数p[++m] = n, c[m] = 1;return m;                         //共m个因子
}
int main(){int a, b;   cin >> a >> b;for(int i = a; i <= b; i ++){int m = factor(i);cout << i << "=";for(int j = 1; j <= m; j ++)  //第j个因子{ for(int k = 1; k <= c[j]; k ++)//第j个因子的个数{    cout << p[j];if(k < c[j]) cout << "*";}if(j < m) cout << "*";}cout << endl;}return 0;
}

这篇关于【No.20】蓝桥杯简单数论下|寻找整数|素数的判断|笨小猴|最大最小公倍数|素数筛|埃氏筛|欧氏线性筛|质数|分解质因子(C++)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/851967。

相关文章

C++统计函数执行时间的最佳实践

C++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法
阅读更多...
如何通过try-catch判断数据库唯一键字段是否重复

如何通过try-catch判断数据库唯一键字段是否重复

《如何通过try-catch判断数据库唯一键字段是否重复》在MyBatis+MySQL中,通过try-catch捕获唯一约束异常可避免重复数据查询,优点是减少数据库交互、提升并发安全,缺点是异常处理开... 目录1、原理2、怎么理解“异常走的是数据库错误路径，开销比普通逻辑分支稍高”？1. 普通逻辑分支 v
阅读更多...
Python 基于http.server模块实现简单http服务的代码举例

Python 基于http.server模块实现简单http服务的代码举例

《Python基于http.server模块实现简单http服务的代码举例》Pythonhttp.server模块通过继承BaseHTTPRequestHandler处理HTTP请求,使用Threa... 目录测试环境代码实现相关介绍模块简介类及相关函数简介参考链接测试环境win11专业版python
阅读更多...
深入解析C++ 中std::map内存管理

深入解析C++ 中std::map内存管理

《深入解析C++中std::map内存管理》文章详解C++std::map内存管理,指出clear()仅删除元素可能不释放底层内存,建议用swap()与空map交换以彻底释放,针对指针类型需手动de... 目录1️、基本清空std::map2️、使用 swap 彻底释放内存3️、map 中存储指针类型的对象
阅读更多...
从基础到进阶详解Python条件判断的实用指南

从基础到进阶详解Python条件判断的实用指南

《从基础到进阶详解Python条件判断的实用指南》本文将通过15个实战案例,带你大家掌握条件判断的核心技巧,并从基础语法到高级应用一网打尽,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录​引言：条件判断为何如此重要一、基础语法：三行代码构建决策系统二、多条件分支：elif的魔法三、
阅读更多...
C++ STL-string类底层实现过程

C++ STL-string类底层实现过程

《C++STL-string类底层实现过程》本文实现了一个简易的string类,涵盖动态数组存储、深拷贝机制、迭代器支持、容量调整、字符串修改、运算符重载等功能,模拟标准string核心特性,重点强... 目录实现框架一、默认成员函数1.默认构造函数2.构造函数3.拷贝构造函数(重点)4.赋值运算符重载函数
阅读更多...
C++ vector越界问题的完整解决方案

C++ vector越界问题的完整解决方案

《C++vector越界问题的完整解决方案》在C++开发中,std::vector作为最常用的动态数组容器,其便捷性与性能优势使其成为处理可变长度数据的首选,然而,数组越界访问始终是威胁程序稳定性的... 目录引言一、vector越界的底层原理与危害1.1 越界访问的本质原因1.2 越界访问的实际危害二、基
阅读更多...
python连接sqlite3简单用法完整例子

python连接sqlite3简单用法完整例子

《python连接sqlite3简单用法完整例子》SQLite3是一个内置的Python模块,可以通过Python的标准库轻松地使用,无需进行额外安装和配置,：本文主要介绍python连接sqli... 目录1. 连接到数据库2. 创建游标对象3. 创建表4. 插入数据5. 查询数据6. 更新数据7. 删除
阅读更多...
Jenkins的安装与简单配置过程

Jenkins的安装与简单配置过程

《Jenkins的安装与简单配置过程》本文简述Jenkins在CentOS7.3上安装流程,包括Java环境配置、RPM包安装、修改JENKINS_HOME路径及权限、启动服务、插件安装与系统管理设置... 目录www.chinasem.cnJenkins安装访问并配置JenkinsJenkins配置邮件通知
阅读更多...
c++日志库log4cplus快速入门小结

c++日志库log4cplus快速入门小结

《c++日志库log4cplus快速入门小结》文章浏览阅读1.1w次，点赞9次，收藏44次。本文介绍Log4cplus，一种适用于C++的线程安全日志记录API，提供灵活的日志管理和配置控制。文章涵盖... 目录简介日志等级配置文件使用关于初始化使用示例总结参考资料简介log4j 用于Java，log4c
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2