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

蓝桥杯算法基础(32):素数,埃式筛法,快速幂,斐波那契与矩阵幂运算

素数

有些人认为一个人一生中有三个周期,从他或她出生的那一天开始。
这三个周期是身体周期,情感周期的和智力的周期,他们有周期的长度为23,28,
和33天。每一个周期都有一个高峰。在一个周期的高峰期,
一个人在他/她在相应的领域(身体,情绪或精神)。
例如,如果它是心理曲线,思维过程会更清晰和集中会更容易。
由于三个周期有不同的周期,所以这三个周期的峰值一般发生在不同的时间。
我们想确定何时发生绝对高潮(所有三个周期的峰值发生在同一天)。
因为处于绝对高潮时人各方面均表现优异,因此人们想知道绝对高潮在哪一天出现。
对身体周期,情绪周期和智力周期,给出本年内他们各自的一个高潮日(不一定是第一个)后经过的天数p,e,i。另外,给出本年内已经经过的天数d(d>=0).求出在d所代表的日期多少天后,
三种周期的高潮日又一次在同一天出现。输入:输入数据有多组,每组测试数据占一行,有四个整数,p,e,i和d.  p,e,i 分别代表从0开始计时,身体周期,情感周期和智力周期首次出现高潮的日期,要求编程计算经过d后多少天第一个绝对高潮出现,输入保证绝对高潮在21252内的某一天出现。输入以-1,-1,-1结束。输出:例如:Case 1: the next triple peak occurs in 1234 days.23 28 33
d1 d2 d3d1+23k1=x
d2+28k2=x
d3+33k3=xx≡d1 %23≡d2 %28≡d3 %33//延续上体的解题方法
//逐级合并法
x=a1(%m1)=a2(%m2)=a3(%m3)
x=a1+m1y1 (1)
x=a2+m2y2
==>m1y1-m2y2=a2-a1这是一个线性方程可解出y1  linearEquation(m1,m2,a2-a1)带回(1).得特解x0=a1+m1*y1-->x=x0+k*lcm(m1,m2)得一个新方程//lcm(m1,m2),m1,m2得公倍数x≡x0 (%lcm(m1,m2))形成新的a(x0),新的m(lcm(m1,m2))public static void main(String[] args)throws Exceeption{Scanner sc= new Scanner(System.in);int t=1;List<long[]> aList=new ArrayList<long[]>();List<long> dList=new ArrayList<long>();while(sc.hasNext()){long[] a={sc.nextLong(),sc.nextLong(),sc.Long()};long d=sc.nextLong();if(a[0]==-1&&a[1]==-1&&a[2]=-1&&d==-1)break;else{aList.add(a);aList.add(d);}}for(int i=0;i<aList.size();i++){long[] a=aList.get(i);long d=dList.get(i);long[] m={23,28,33};long res=Case05_ExtGcd.linearEquationGroup(a,m);while(res<=d){res+=21252;//保证在21252内,就是以21252为模}System.out.println("Case"+(t++)+": the next triple peak occurs in"+(res-d)+"days");}}

埃式筛法

public static void mian(){long now=System.currentTimeMillis();m1(100000);System.out.println(”耗时“+(System.currentTimeMillis()-now)+"ms" );
}private static void  m1(int N){//N是第N个素数//已知在整数X内大概有x/log(X)个素数//现在我们要逆推,要想求第N个素数,我们的整数范围是社么//length就是整数范围int n=2;while(n/log(n)<N){//n个数中,大概有n/log(n)个素数n++;}//开辟一个数组,下标是自然数,值是标记//基本思路是筛选法,把非素数标记出来//int[] arr=new int[n];int x=2;while(x<n){//标记过了。继续下一个if(arr[x]!=0){continue;}int k=2;//对每个x,我们都从2倍开始,对x的k倍,全部标记-1while(x*k<n){arr[x*k]=-1;k++;}x++;}//System.out,println(arr);//筛完之后,这个很长的数组里面非素数下标对应的值都是-1int sum=0;for(int i=2;i<arr.length;i++){//是素数,计数+1if(arr[i]==0){sum++;}if(sum==N){System.out,println(i);}}
}

 快速幂

反复平方
a^10    8 0 2 01 0 1 0
a^(2^3) a^(2^2) a^(2^1) a^(a^0);将次方转成二进制,哪一位有1,就乘以那一位所在的a的平方值
如 a^10=a^(2^3)*a(2^1)public static long ex2(long n,long m){long primeFangShu = n;//n的1次方long result=1;while(m!=0){if((m&1)==1){result*=pingFangShu;//每移位一次,幂累成方一次pingFangShu=pingFangShu*pingFangShu;//无论等不等于1,次方都成倍乘//右移一位m>>=1;}return result;}}

 斐波那契与矩阵幂运算

(f1.f2)=(1,1)(f1,f2)*[0 1]=[f2.f3] //0+1=1=f1,1+1=2=f3=f1+f2[1 1](f1.f2)*[0 1]^2=[f3,f4][1 1]....递推[f1,f2]*[0 1]^n-1=[fn,fn+1][1 1]public static long fib(long n){if(n==1||n==2)return1;long[][] matrix={{0,1},{1,1}};long[][] res=Util.matrixPower(matrix,n-1);//矩阵的乘方res=Util.matrixMultiply(new long[][]{(1,1)},res);//矩阵的乘方与f1f2相乘return res[0][0];}public long[][] matrixPower(long[][] matrix,long p){//初始化结果为单位矩阵,对角线为1
long[][] result=new long[matrix.length][matrix[0].length];
//单位矩阵。相当于整数的1for(int i=0;i<result.length;i++){result[i][i]=1;}//平方数
long[][] pingFang=matrix;//一次方for(;p!=0;p++){while(p!=0){if((p&1)!=0){//当前二进制最低位1,将当前平方数乘到结果中result=matrixMultiply(result,pingFang);}平方数继续上翻pinFang=matrixMultiply(pingFang,pingFang);p>>1;}return result;
}}

相关文章:

蓝桥杯算法基础(32):素数,埃式筛法,快速幂,斐波那契与矩阵幂运算

素数 有些人认为一个人一生中有三个周期&#xff0c;从他或她出生的那一天开始。 这三个周期是身体周期&#xff0c;情感周期的和智力的周期&#xff0c;他们有周期的长度为23&#xff0c;28&#xff0c; 和33天。每一个周期都有一个高峰。在一个周期的高峰期&#xff0c; 一个…...

VSCode - 离线安装扩展python插件教程

1&#xff0c;下载插件 &#xff08;1&#xff09;首先使用浏览器打开 VSCode 插件市场link &#xff08;2&#xff09;进入插件主页&#xff0c;点击右侧的 Download Extension 链接&#xff0c;将离线安装包下载下来&#xff08;文件后缀为 .vsix&#xff09; 2&#xff0c;…...

2024年中级职称现在报名,时间还太早了吗?什么时候合适?

甘建二十年耕耘职称&#xff0c;关于职称大小事都了解 想要评湖北职称&#xff0c;请认准甘建二&#xff0c;关于职称评审条件、申报时间、评审资料、申报材料、评审流程、证书查询、出证时间、考试答辩等关于职称所有的事情都知道&#xff0c;找甘建二准没错。 我们通常都会觉…...

《责任链模式(极简c++)》

本文章属于专栏- 概述 - 《设计模式&#xff08;极简c版&#xff09;》-CSDN博客 模式说明 方案&#xff1a; 责任链模式将请求的发送者和接收者解耦&#xff0c;构成一个链条&#xff0c;并由多个对象对请求进行处理&#xff0c;直到找到合适的处理者为止。优点&#xff1a; …...

【学习】JMeter和Postman两种测试工具的主要区别有哪些

Postman和JMeter都是常用的API测试工具&#xff0c;但它们之间存在一些不同之处。以下是Postman和JMeter的主要区别&#xff1a; 语言支持 Postman是一个基于Chrome的应用程序&#xff0c;因此它使用JavaScript作为编程语言。这意味着你可以使用JavaScript来编写测试脚本和断…...

【压缩字符串算法解析与实现】

压缩的要求是将连续相同字符替换为字符 数字形式&#xff0c;例如 “AAABCCDDDD” 变为 “A3BC2D4”。 问题描述与分析 给定一个字符串&#xff0c;我们需要判断是否可以进行压缩&#xff0c;并且只在压缩后的字符串长度比原字符串长度更短时进行压缩。如果字符串可以压缩&a…...

test02

欢迎关注博主 Mindtechnist 或加入【Linux C/C/Python社区】一起学习和分享Linux、C、C、Python、Matlab&#xff0c;机器人运动控制、多机器人协作&#xff0c;智能优化算法&#xff0c;滤波估计、多传感器信息融合&#xff0c;机器学习&#xff0c;人工智能等相关领域的知识和…...

K8S Pod 水平自动扩缩容 HPA

介绍 HPA&#xff08;Horizontal Pod Autoscaler&#xff09;水平扩缩意味着可根据观察到的CPU、内存使用率或自定义度量标准来自动扩展或缩容Pod的数量&#xff08;Deployment、StatefulSet 或其他类似资源&#xff09;。与“垂直”扩缩不同&#xff0c;对于 K8S&#xff0c;…...

Spring日志框架

前言 本文我们简单说说关于Spring中的日志框架,以及对应的注解 我们知道,公司服务器在运行的时候,一定会打印日志,有很多优点,比如预防报警,或者是某重大事故尝试修复等等都需要查看日志 应该说日志对我们来说并不陌生,我们在之前刷题或者是程序遇到bug的时候也经常会将程序的状…...

(九)关系数据理论

函数依赖&#xff1a;设R(U)是属性集U上的关系模式。X、Y是属性集U的子集。若对于R(U)的任意一个可能的关系r&#xff0c;r中不可能存在两个元组在X上的属性值相等&#xff0c;而在Y上的属性值不等&#xff0c;则称X函数确定Y或Y函数依赖于X&#xff0c;记作X→Y。(即只要X 上的…...

【经验分享】Ubuntu下如何解决问题arm-linux-gcc:未找到命令

【经验分享】Ubuntu下如何解决问题arm-linux-gcc&#xff1a;未找到命令 前言问题分析解决方法 前言 在编译过程中发现一个问题&#xff0c;明明之前安装了gcc-4.6版本&#xff0c;版本信息都是正常显示的&#xff0c;刚安装上去的时候也是可以用的。但不知道什么原因突然不能…...

【算法刷题day10】Leetcode:232.用栈实现队列、225. 用队列实现栈

文章目录 Leetcode 232.用栈实现队列解题思路代码总结 Leetcode 225. 用队列实现栈解题思路代码总结 stack、queue和deque对比 草稿图网站 java的Deque Leetcode 232.用栈实现队列 题目&#xff1a;232.用栈实现队列 解析&#xff1a;代码随想录解析 解题思路 一个栈负责进&a…...

sql注入详解

ps:简单说下这里只写了我能理解的明白的&#xff0c;后面的二阶注入&#xff0c;堆叠注入没写 手工sql注入 1.存在sql注入本质上就是数据库过滤的不严格或者未进行过滤&#xff0c;1 and 11&#xff0c;返回正常&#xff0c;1 and 12 返回不正常&#xff0c;说明带到数据库里面…...

[蓝桥杯 2022 省 B] 李白打酒加强版

题目链接 [蓝桥杯 2022 省 B] 李白打酒加强版 题目描述 话说大诗人李白&#xff0c;一生好饮。幸好他从不开车。 一天&#xff0c;他提着酒壶&#xff0c;从家里出来&#xff0c;酒壶中有酒 2 2 2 斗。他边走边唱&#xff1a; 无事街上走&#xff0c;提壶去打酒。 逢店加一倍…...

【检索增强】Retrieval-Augmented Generation for Large Language Models:A Survey

本文简介 1、对最先进水平RAG进行了全面和系统的回顾&#xff0c;通过包括朴素RAG、高级RAG和模块化RAG在内的范式描述了它的演变。这篇综述的背景下&#xff0c;更广泛的范围内的法学硕士研究RAG的景观。 2、确定并讨论了RAG过程中不可或缺的核心技术&#xff0c;特别关注“…...

EVM Layer2 主流解决方案

深度解析主流 EVM Layer 2 解决方案&#xff1a;zk Rollups 和 Optimistic Rollups 随着以太坊网络的不断演进和 DeFi 生态系统的迅速增长&#xff0c;以太坊 Layer 2 解决方案日益受到关注。 其中&#xff0c;zk Rollups 和 Optimistic Rollups 作为两种备受瞩目的主流 EVM&…...

go中结构体标签:omitempty、json꞉“name“、 gorm꞉“column꞉name“、yaml꞉“name“

在Go语言中&#xff0c;结构体标签&#xff08;Struct Tags&#xff09;提供了一种在编译时附加到结构体字段上的元数据&#xff0c;这些标签可以被运行时的反射&#xff08;reflection&#xff09;机制读取。结构体标签的存在意义和用途非常广泛&#xff0c;主要包括&#xff…...

七月论文审稿GPT第4版:通过paper-review数据集微调Mixtral-8x7b,对GPT4胜率超过80%

前言 在此之前&#xff0c;我司论文审稿项目组已经通过我司处理的paper-review数据集&#xff0c;分别微调了RWKV、llama2、gpt3.5 16K、llama2 13b、Mistral 7b instruct、gemma 7b 七月论文审稿GPT第1版&#xff1a;通过3万多篇paper和10多万的review数据微调RWKV七月论文审…...

【QT学习】1.qt初识,创建qt工程,使用按钮,第一个交互按钮

1.初识qt--》qt是个框架&#xff0c;不是语言 1.学习路径 一 QT简介 &#xff0c;QTCreator &#xff0c;QT工程 &#xff0c;QT的第一个程序&#xff0c;类&#xff0c;组件 二 信号与槽 三 对话框 四 QT Desiner 控件 布局 样式 五 事件 六 GUI绘图 七 文件 八 …...

JavaScript_与html结合方式

JavaScript_语法 ECMAScript&#xff1a;客户端脚本语言的标准 1.基本语法 1.1 与html结合方式&#xff08;2种&#xff09; 1. 内部JS 定义<script>,标签体内容就是js代码 2. 外部JS 定义<script>,通过src属性引入外部的 js文件 注意&#xff1a; 1.<script>…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...