【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。

相关文章

Java判断多个时间段是否重合的方法小结

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...
redis群集简单部署过程

redis群集简单部署过程

《redis群集简单部署过程》文章介绍了Redis,一个高性能的键值存储系统,其支持多种数据结构和命令,它还讨论了Redis的服务器端架构、数据存储和获取、协议和命令、高可用性方案、缓存机制以及监控和... 目录Redis介绍1. 基本概念2. 服务器端3. 存储和获取数据4. 协议和命令5. 高可用性6.
阅读更多...
c++中std::placeholders的使用方法

c++中std::placeholders的使用方法

《c++中std::placeholders的使用方法》std::placeholders是C++标准库中的一个工具,用于在函数对象绑定时创建占位符,本文就来详细的介绍一下,具有一定的参考价值,感兴... 目录1. 基本概念2. 使用场景3. 示例示例 1：部分参数绑定示例 2：参数重排序4. 注意事项5.
阅读更多...
使用C++将处理后的信号保存为PNG和TIFF格式

使用C++将处理后的信号保存为PNG和TIFF格式

《使用C++将处理后的信号保存为PNG和TIFF格式》在信号处理领域,我们常常需要将处理结果以图像的形式保存下来,方便后续分析和展示,C++提供了多种库来处理图像数据,本文将介绍如何使用stb_ima... 目录1. PNG格式保存使用stb_imagephp_write库1.1 安装和包含库1.2 代码解
阅读更多...
JAVA调用Deepseek的api完成基本对话简单代码示例

JAVA调用Deepseek的api完成基本对话简单代码示例

《JAVA调用Deepseek的api完成基本对话简单代码示例》：本文主要介绍JAVA调用Deepseek的api完成基本对话的相关资料,文中详细讲解了如何获取DeepSeekAPI密钥、添加H... 获取API密钥首先，从DeepSeek平台获取API密钥，用于身份验证。添加HTTP客户端依赖使用Jav
阅读更多...
C++实现封装的顺序表的操作与实践

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...
使用C++实现单链表的操作与实践

使用C++实现单链表的操作与实践

《使用C++实现单链表的操作与实践》在程序设计中,链表是一种常见的数据结构,特别是在动态数据管理、频繁插入和删除元素的场景中,链表相比于数组,具有更高的灵活性和高效性,尤其是在需要频繁修改数据结构的应... 目录一、单链表的基本概念二、单链表类的设计1. 节点的定义2. 链表的类定义三、单链表的操作实现四、
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2