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

算法比赛——必备的数论知识

秋名山码民的主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
🙏作者水平有限,如发现错误,还请私信或者评论区留言!

目录

  • 一、欧几里得
  • 二、扩展欧几里得
  • 三、算术基本定理
  • 四、线性筛选求质数
  • 五、等差数列
  • 六、等比数列
  • 七、组合计数
  • 最后


一、欧几里得

求最大公约数的一种常用方法

public static int gcd(int a, int b) {return b != 0 ? gcd(b, a % b) : a;
}

二、扩展欧几里得

求x,y使得ax+by = gcd(a,b)

	public static int exGcd(int a,int b,int x,int y){if(b == 0){x = 1;y = 0;return a;}int d = exGcd(b,a%b,y,x);y -= (a/b)*x;return d;}

三、算术基本定理

算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数,要么本身就是质数,要么可以写为2个或以上的质数的积,而且这些质因子按大小排列之后,写法仅有一种方式。
在这里插入图片描述
证明参考:维基百科

四、线性筛选求质数

在O(N)的时间复杂度内,求出来1 ~ n中所有的质数,以及每一个数的最小质因子。

	private static void get_primes(int n) {for (int i = 2; i <= n; i++) {if (!st[i]) primes[cnt++] = i;for (int j = 0; primes[j] * i <= n; j++) {/*因为prime中素数是递增的,所以如果i%prime[j]!=0代表i的最小质因数还没有找到,即i的最小质因数大于prime[j]也就是说prime[j]就是i*prime[j]的最小质因数,于是i*prime[j]被它的最小质因数筛掉了*/st[primes[j] * i] = true; // 把质数的i倍筛掉/*如果当i%prime[j]==0时,代表i的最小质因数是prime[j],那么i*prime[j+k](k>0)这个合数的最小质因数就不是prime[j+k]而是prime[j]了所以i*prime[j+k]应该被prime[j]筛掉,而不是后续的prime[j+k],于是在此时break*/if (i % primes[j] == 0) break; // 通过最小质因子来筛}}}

五、等差数列

这俩个数列,学过高中数学的应该都清楚,我就不加以证明了。

1246. 等差数列

import java.util.Arrays;
import java.util.Scanner;/*** @Author 秋名山码神* @Date 2023/2/17* @Description*/
public class Main {static int N = 100010;static int[] a = new int[N];public static int gcd(int a,int b){return b != 0 ? gcd(b,a%b) : a;//b!=0 , 递归计算gcd(b,a%b)}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();for(int i = 0; i<n; i++)a[i] = sc.nextInt();Arrays.sort(a,0,n);int d = 0;for(int i = 1; i<n; i++)d = gcd(d,a[i] - a[0]);if(d == 0){System.out.println(n);}else {System.out.println((a[n-1] - a[0]) / d + 1);}}
}

六、等比数列

P8636 蓝桥杯 2016 省 AB 最大比例

#include<iostream>
#include<algorithm>using namespace std;const int N=110;typedef long long LL;LL x[N],a[N],b[N];
int cnt=0;//假设原数列为 a,a*(p/q)^1,a*(p/q)^2,...,a*(p/q)^(n-1)
//假设抽取的数列  b0,b1,...,b(N-1)  (从小到大排好序了)
//  b1/b0,b2/b0,...,b(N-1)/b0-->  (p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)
//  我们要求的是:  (p/q)^k  (p/q)>1,所以使k最大,即求 x1~x(N-1)的最大公约数
//这里我们使用更相减损术,因为我们没有得到确切的x1~x(N-1)是多少,我们只有(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)这些的值/*更相减损术:第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。*///更相减损术总用较大的减去较小的
/*例子:98-63=3563-35=2835-28=728-7=2121-7=1414-7=7
所以,98和63的最大公约数等于7。*///我们这里要用更相减损术的是指数,所以要让(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1),两两计算,互除,除到结果为1,即x1=x2,此时幂次为0,结果为1,这其实就是y总的思路,再次感叹y总的才华
//把分子分母分别去算,结果是相同的因为,分子分母的幂次是相同的
LL gcd(LL a,LL b)
{return b? gcd(b,a%b):a;
}LL gcd_sub(LL a,LL b)  
{if(a<b)  swap(a,b);  //更相减损术总是大减小(它们的底数是一样的)if(b==1)  return a;return gcd_sub(b,a/b);
}int main()
{int n;cin>>n;for(int i=0; i<n; i++)  scanf("%lld",&x[i]);sort(x,x+n);for(int i=1; i<n; i++){if(x[i] != x[i-1]){LL d=gcd(x[i],x[0]);  a[cnt]=x[i] / d;  //得到x[i]/x[0]的分子b[cnt]=x[0] / d;  //得到x[i]/x[0]的分母cnt++;}}LL up=a[0],down=b[0];for(int i=1; i<cnt; i++){up=gcd_sub(up,a[i]);  //两两求最大公约数down=gcd_sub(down,b[i]);}cout<<up<<"/"<<down<<endl;return 0;
}

七、组合计数

加法原理 : 若完成一件事的方法有n类,其中第i类方法包括ai种不同的方法,且这些方法互不重合,则完成这件事共有a1+a2+…+an种不同的方法。
乘法原理 :若完成一件事,需要n个步骤,其中第i个步骤有ai种不同的完成方法,且这些步骤互不干扰,则完成这件事共有a1a2…*an种不同的方法

排列数 : 从n个不同的元素中依次取出m个元素排成一列,产生的不同排列的数量为:

在这里插入图片描述
组合数 : 从n个元素中取出m个元素组成一个集合(不考虑顺序),产生的不同集合的数量为:
在这里插入图片描述
计算系数

//杨辉三角做法:
#include<iostream>
using namespace std;
long long x[1010][1010];
int main()
{long long a,b,k,n,m;cin>>a>>b>>k>>n>>m;x[1][1]=1;for(int i=2;i<=k+1;i++) for(int j=1;j<=i;j++)x[i][j]=(x[i-1][j-1]*b+x[i-1][j]*a)%10007;cout<<x[k+1][m+1];return 0;
}

二项式做法

最后

数论的知识太多了,这是我最近三天想到的,后续有时间再补充吧!
请添加图片描述

相关文章:

算法比赛——必备的数论知识

秋名山码民的主页 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; &#x1f64f;作者水平有限&#xff0c;如发现错误&#xff0c;还请私信或者评论区留言&#xff01; 目录一、欧几里得二、扩展欧几里得三、算术基本定理四、线性筛选求质数五…...

Docker概述

什么是Docker我们要学习在Linux(RockyLinux)中安装使用Docker来配置软件的功能Docker是一个用来开发、运输和运行应用程序的开放平台。使用Docker可以将应用程序与基础结构分离&#xff0c;以便快速交付软件。使用Docker&#xff0c;您可以以管理应用程序的方式管理基础架构。通…...

实验室设计建设方案主要内容

实验室设计建设整体解决方案SICOLAB需要综合考虑实验室的功能需求、空间布局、设备选型、安全防护、节能环保等多方面因素。以下是一个基本的实验室设计建设方案的流程&#xff1a;一、需求分析&#xff1a;了解实验室的使用目的、实验内容、使用人数、设备种类、实验标准等&am…...

华为OD机试真题Python实现【日志采集系统】真题+解题思路+代码(20222023)

日志采集系统 题目 日志采集是运维系统的的核心组件。日志是按行生成,每行记做一条,由采集系统分批上报。 如果上报太频繁,会对服务端造成压力; 如果上报太晚,会降低用户的体验; 如果一次上报的条数太多,会导致超时失败。 为此,项目组设计了如下的上报策略: 每成功上…...

Python的模块与工具包

模块 模块是一个Python文件&#xff0c;以 .py结尾。模块能定义函数&#xff0c;类和变量&#xff0c;模块里也能包含可执行的代码。 作用 python 中有很多各种不同的模块&#xff0c;每一个模块都可以帮助我们快速的实现一些功能&#xff0c;比如实现和时间相关的功能就可以…...

联合熵和条件熵

本专栏包含信息论与编码的核心知识&#xff0c;按知识点组织&#xff0c;可作为教学或学习的参考。markdown版本已归档至【Github仓库&#xff1a;information-theory】&#xff0c;需要的朋友们自取。或者公众号【AIShareLab】回复 信息论 也可获取。 文章目录联合熵条件熵联合…...

华为OD机试真题Python实现【求最大数字】真题+解题思路+代码(20222023)

求最大数字 题目 给定一个由纯数字组成以字符串表示的数值,现要求字符串中的每个数字最多只能出现2次,超过的需要进行删除;删除某个重复的数字后,其它数字相对位置保持不变。 如34533,数字3重复超过2次,需要删除其中一个3,删除第一个3后获得最大数值4533 请返回经过删…...

Python爬虫(10)selenium爬虫后数据,存入csv、txt并将存入数据并对数据进行查询

之前的文章有关于更多操作方式详细解答&#xff0c;本篇基于前面的知识点进行操作&#xff0c;如果不了解可以先看之前的文章 Python爬虫&#xff08;1&#xff09;一次性搞定Selenium(新版)8种find_element元素定位方式 Python爬虫&#xff08;2&#xff09;-Selenium控制浏览…...

Python 之 Pandas 时间函数 time 、datetime 模块和时间处理基础

文章目录一、time 模块1、时间格式转换图2. struct_time 元组元素结构3. format time 结构化表示二、datetime 模块1. date类2. 方法和属性3. datetime 类三、timedelta 类的时间加减四、时间处理基础Python 中提供了对时间日期的多种多样的处理方式&#xff0c;主要是在 time …...

C语言学习及复习笔记-【5】C 运算符

文章目录5. C 运算符5.1 关系运算符5.2 逻辑运算符5.3 位运算符5.4 杂项运算符 ↦ sizeof & 三元5.5 例子1). 利用异或 ^ 来交换两个数的值&#xff0c;而且不引入其他变量。2). 利用位与 & 运算&#xff0c;判断一个整数是否是2的整数次幂。3). 不同长度的数据进行位运…...

数仓、数据湖、湖仓一体、数据网格

第一代&#xff1a;数据仓库 定义 为解决数据库面对数据分析的不足&#xff0c;孕育出新一类产品数据仓库。数据仓库&#xff08;Data Warehouse&#xff09;是一个面向主题的、集成的、相对稳定的、反映历史变化的数据集合&#xff0c;用于支持管理决策和信息的全局共享。 数…...

C语言【atoi函数】

C语言【atoi函数】&#x1fac5;系统atoi函数&#x1fac5; 模拟实现atoi函数看到atoi函数&#xff0c;有人又会问有这个函数&#xff0c;我怎么没用过。那就说明&#xff1a;不是你刷题太少&#xff0c;就是atoi函数存在感太低。 这篇函数就带你领略atoi函数的魅力 &#x1fa…...

一起学习用Verilog在FPGA上实现CNN----(八)integrationFC设计

1 integrationFC设计 LeNet-5网络结构全连接部分如图所示&#xff0c;该部分有2个全连接层&#xff0c;1个TanH激活层&#xff0c;1个SoftMax激活层&#xff1a; 图片来自附带的技术文档《Hardware Documentation》 integrationFC部分原理图&#xff0c;如图所示&#xff0c;…...

面试题总结

1.js的数据类型 分为基本数据类型和引用数据类型。 基本数据类型 ES5的5种&#xff1a;Null&#xff0c;undefined&#xff0c;Boolean&#xff0c;Number&#xff0c;String&#xff0c; ES6新增&#xff1a;Symbol表示独一无二的值 ES10新增&#xff1a;BigInt 表示任意大的…...

go进阶(1) -深入理解goroutine并发运行机制

并发指的是同时进行多个任务的程序&#xff0c;Web处理请求&#xff0c;读写处理操作&#xff0c;I/O操作都可以充分利用并发增长处理速度&#xff0c;随着网络的普及&#xff0c;并发操作逐渐不可或缺 一、goroutine简述 在Golang中一个goroutines就是一个执行单元&#xff…...

mongodb 操作记录

#启动服务 net start MongoDB #停止服务 net stop MongoDB #进入mongo shell 方式 mongo db #查看当前数据库是那个 #插入一条数据 db.runoob.insert({x:10}) #查找数据 db.runoob.find() 查询所有的数据库 show dbs #连接mongodb mongodb://[username:password]host1[:po…...

JDBC简单的示例

JDBC 编程步骤 加载驱动程序&#xff1a; Class.forName(driverClass) //加载MySql驱动 Class.forName("com.mysql.jdbc.Driver") //加载Oracle驱动 Class.forName("oracle.jdbc.driver.OracleDriver")获得数据库连接&#xff1a; DriverManager.getCon…...

Spring架构篇--2.3 远程通信基础--IO多路复用select,poll,epoll模型

前言&#xff1a;对于传统的BIO&#xff08;同步阻塞&#xff09;模型&#xff0c;当有客户端连接达到服务端&#xff0c;服务端在对改连接进行连接建立&#xff0c;和数据传输过程中&#xff0c;是无法响应其他客户端的&#xff0c;只有当服务端完成对一个客户端处理后&#x…...

python--matplotlib(4)

前言 Matplotlib画图工具的官网地址是 http://matplotlib.org/ Python环境下实现Matlab制图功能的第三方库&#xff0c;需要numpy库的支持&#xff0c;支持用户方便设计出二维、三维数据的图形显示&#xff0c;制作的图形达到出版级的标准。 其他matplotlib文章 python--matpl…...

【项目精选】城市公交查询系统(论文+视频+源码)

点击下载源码 1.1 选题背景 随着低碳生活的普及&#xff0c;人们更倾向于低碳环保的出行方式&#xff0c;完善公交系统无疑具有重要意义。公交是居民日常生活中最常使用的交通工具之一&#xff0c;伴随着我国经济繁荣和城市人口增长&#xff0c;出行工具的选择也变得越来越重要…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...