【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} 11017的每个数
由于这个数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=n2n1=2(a2a1)=3(b2b1)
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 的倍数,得{234,5,6,7,8910,11,12,13,…}
  3. 输出最小的素数 5,筛掉 5 的倍数,得{23456,7,8910,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=p1c1p2c2p3c3pmcm​,其中 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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/287653.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

深度学习pytorch——减少过拟合的几种方法(持续更新)

1、增加数据集 2、正则化(Regularization) 正则化&#xff1a;得到一个更加简单的模型的方法。 以一个多项式为例&#xff1a; 随着最高次的增加&#xff0c;会得到一个更加复杂模型&#xff0c;模型越复杂就会更好的拟合输入数据的模型&#xff08;图-1&#xff09;&#…

2024品牌私域运营:「去中心化」正在成为企业决胜关键

越来越多的品牌选择以DTC模式与消费者互动和销售。通过与消费者建立紧密联系&#xff0c;不仅可提供更具成本效益的规模扩张方式&#xff0c;还能控制品牌体验、获取宝贵的第一方数据并提升盈利能力。许多企业采取的DTC私域策略以交易为中心的方法往往导致了成本上升和运营复杂…

Day18:LeedCode 513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树

513. 找树左下角的值 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 思路:出该二叉树的 最底层 最左边 节点的值找出深度最大的第一个结点(左结点先遍历) 方法一…

发送请求- header配置

请求头里是客户端的要求&#xff0c;把你的诉求告诉服务端&#xff0c;服务端按照你的要求返回数据 &#xff0c; 请求header需要严格全配置&#xff0c;把请求header全部传入&#xff0c;不能频繁访问&#xff0c;让后端知道它是正常请求 一般只配置User-Agent和Content Typ…

模板方法模式(继承的优雅使用)

目录 前言 UML plantuml 类图 实战代码 AbstractRoutingDataSource DynamicDataSource DynamicDataSourceContextHolder 前言 在设计类时&#xff0c;一般优先考虑使用组合来替代继承&#xff0c;能够让程序更加的灵活&#xff0c;但这并不意味着要完全抛弃掉继承。 …

2024/3/26 C++作业

定义一个矩形类&#xff08;Rectangle&#xff09;&#xff0c;包含私有成员&#xff1a;长(length)、宽&#xff08;width&#xff09;, 定义成员函数&#xff1a; 设置长度&#xff1a;void set_l(int l) 设置宽度&#xff1a;void set_w(int w) 获取长度&#xff1a;int…

Python批量提取图像灰度共生矩阵(GLCM)、支持批量处理、任意图像格式

目录 一、介绍 二、实现 1、特征计算 2、批量处理 3、结果 一、介绍 灰度共生矩阵(Grey Level Co-occurrence Matrix)也叫做空间灰度级依赖矩阵(SGLDM),它是一种基于统计的纹理特征提取的方法。 一般包括四个方向&#xff1a; (a,b)(1,0)&#xff0c;像素对是水平的&am…

基于javaweb(springboot+mybatis)生活美食分享平台管理系统设计和实现以及文档报告

基于javaweb(springbootmybatis)生活美食分享平台管理系统设计和实现以及文档报告 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 …

在django中使用kindeditor出现转圈问题

在django中使用kindeditor出现转圈问题 【一】基础检查 【1】前端检查 确保修改了uploadJson的默认地址 该地址需要在路由层有映射关系 确认有加载官方文件 kindeditor-all-min.js确保有传递csrfmiddlewaretoken 或者后端关闭了csrf验证 <textarea name"content&qu…

AXI-Stream——草稿版

参考自哔站&#xff1a;FPGA IP之AXI4-Lite AXI4-Stream_哔哩哔哩_bilibili 信号 传输层级从小到大 包(----------transfer--transfer--------)------delay--------包(----------transfer--transfer--------) TKEEP和TSTRB共同决定了是哪种数据流

Github简单入门教程

文章目录 使用前提查看项目内容查看项目介绍打包下载项目查看项目作者项目搜索复制项目分支项目创建向项目中添加文件对项目进行评论 使用前提 想要使用Github&#xff0c;首先需要学会科学上网&#xff0c;不然用国内的网在正规情况下是无法访问Github滴~ 查看项目内容 打开…

鸿蒙Harmony应用开发—ArkTS-ForEach:循环渲染

ForEach基于数组类型数据执行循环渲染。 说明&#xff1a; 从API version 9开始&#xff0c;该接口支持在ArkTS卡片中使用。 接口描述 ForEach(arr: Array,itemGenerator: (item: Array, index?: number) > void,keyGenerator?: (item: Array, index?: number): string …

批量重命名文件名,一键翻译重命名并复制到指定文件夹,高效整理无烦恼

在信息爆炸的时代&#xff0c;高效、智能的文件管理已成为职场和生活中的必备技能。然而&#xff0c;传统的文件管理方法往往耗时且繁琐。现在&#xff0c;我们带来了一款全新的解决方案&#xff0c;让您可以轻松实现文件的翻译、重命名和复制到指定文件夹&#xff0c;为您的文…

Vue3+.NET6前后端分离式管理后台实战(七)

1&#xff0c;Vue3.NET6前后端分离式管理后台实战(七)已经在订阅号发布有兴趣的可以关注一下&#xff01; 有兴趣的可以关注一下&#xff1a;

基于单片机的智能汽车防盗系统设计

摘要:本文介绍了一种以汽车专用单片机飞思卡尔MC68HC908QT4CPE 作为底层主控芯片,人体远红外热释传感器、防闯入光幕墙及振动传感器作为检测装置的汽车防盗系统。单片机将检测到的防盗传感器开关信号,通过数据分析,系统可以设置布防和解除布防模式,在布防模式下,当检测到…

mysql安装及操作

一、Mysql 1.1 MySQL数据库介绍 1.1.1 什么是数据库DB&#xff1f; DB的全称是database&#xff0c;即数据库的意思。数据库实际上就是一个文件集合&#xff0c;是一个存储数据的仓库&#xff0c;数据库是按照特定的格式把数据存储起来&#xff0c;用户可以对存储的数据进行…

[HackMyVM]靶场Crossbow

kali:192.168.56.104 靶机:192.168.56.136 端口扫描 # nmap 192.168.56.136 Starting Nmap 7.94SVN ( https://nmap.org ) at 2024-03-26 22:17 CST Nmap scan report for crossbow.hmv (192.168.56.136) Host is up (0.0057s latency). Not shown: 997 closed tcp…

STM32F103 CubeMX 使用USB生成键盘设备

STM32F103 CubeMX 使用USB生成键盘设备 基础信息HID8个数组各自的功能 生成代码代码编写添加申明信息main 函数编写HID 修改1. 修改报文描述符2 修改 "usbd_hid.h" 中的申明文件 基础信息 软件版本&#xff1a; stm32cubmx&#xff1a;6.2 keil 5 硬件&#xff1a;…

(二)Eureka服务搭建,服务注册,服务发现

1.Eureka注册中心 假如我们的服务提供者user-service部署了多个实例&#xff0c;如图&#xff1a; 存在几个问题&#xff1a; order-service在发起远程调用的时候&#xff0c;该如何得知user-service实例的ip地址和端口&#xff1f;有多个user-service实例地址&#xff0c;…

【探究图论中dfs记忆化,搜索,递推,回溯关系】跳棋,奶牛隔间, 小A和uim之大逃离 II

本篇很高能&#xff0c;如有错误欢迎指出&#xff0c;本人能力有限&#xff08;需要前置知识记忆化dfs&#xff0c;树形dp&#xff0c;bfsdp&#xff0c;tarjan&#xff09; 另外&#xff0c;本篇之所以属于图论&#xff0c;也是想让各位明白&#xff0c;dfs就是就是在跑图&am…