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

Python版本的常见模板(二) 数论(一)

文章目录

  • 前言
  • 质数相关
    • 质数判断
    • 求约数
    • 求取区间质数
      • 埃氏筛法
      • 线性筛法
    • 分解质因数
  • 欧拉
    • 欧拉函数
      • 求取单个数
      • 线性筛法求取
    • 欧拉定理
    • 求逆元
      • 快速幂/幂取模
  • 欧几里得算法
    • 求最小公约数
    • 拓展欧几里得算法
    • 求解同余方程

前言

本文主要是提供Python版本的常见的一些与数论相关的模板,例如求解质数,质因数分解,简单博弈论,以及组合型问题(经典的括号匹配组合问题)等等。至于原理与证明的话,由于存在大量的数学公式推理,因此本文不展示,仅展示代码与变量说明和使用场景。

注意: 相关原理将使用红色字体进行标注,证明可自行查阅资料。本文不再赘述!

质数相关

质数判断

朴素方式:

def isPrim(n):if(n==1):return Falsefor i in range(2,n):if(n%i==0);return Falsereturn True

之后的话,由于除法的一些性质,当 n/d = d 的时候,d^2 = n 在这个循环过程当中 d^2 <= n 这个时候的话,是没有必要全部除去的,只需要一般就好了。

优化版本:

def isPrime(n):if(n==1):return i = 2while(i<=(n//i)):if(n%i==0):return Falsereturn True

求约数

这个的话就是前面说的那句话的比较好的运用

def yueShu(n):i = 1while(i<=n//i):if(n%i==0):print(i)if(i!=n//i):print(n//i)i+=1

此外:
在这里插入图片描述

求取区间质数

现在我们知道了如何判断一个质数,那么现在我们需要求取一个区间内的质数,例如,我们需要求取,从1~n之间所有的质数有哪些?

埃氏筛法

直接看到代码:

def getPrims(n):prime = [0] * (n+1):st = [False] * (n+1)cnt = 0for i in range(2,n+1):if(not st[i]):prime[cnt] = icnt+=1j = i+iwhile(j<=n):st[j] = Truej+=i

这个的话,就是把这个质数的倍数给筛掉。

线性筛法

埃氏筛法的效率还是可以的,但是还可以优化一下。

def getPrim(n):prime = [0] * (n+1):st = [False] * (n+1)cnt = 0for i in range(2,n+1):if(not st[i]):prime[cnt] = icnt+=1j = 0while(prime[j] <=n//i):st[prime[j]*i] = Trueif(i%(prime[j])==0):breakj+=1

这个的话就是把那个筛选的给优化了一下。

分解质因数

ok,接下来是分解质因数,这个分解质因数是很有用的东西。

N = p1^a1 * p2*a2 …pk^ak
对于一个数N都可以拆解为这样的样子,其中这个P是质数

def division(n):i = 2while(i<=n/i):if(n%i==0):a = 0while(n%i==0):n//=ia+=1print("当前质因数为:{},对于的幂是{}".format(i,a))if(n>1):print("当前质因数为:{},对于的幂是{}".format(n,1))

欧拉

这个东西的话和我们的这个质数还是有点关系的。

欧拉函数

欧拉函数φ(5) 表示从1~5 当中和5 互质的元素个数有几个。

求取单个数

同样的和我们刚刚的这个质数是类似的,可以直接求取这个欧拉函数,也有求取一个区间的所有欧拉函数值。
在这里插入图片描述


def OuLa(n):res = ni = 2while(i<=(n//i)):if(n%i==0):while(n%i==0):n//=i#res = res* (1-(1/i)) 优化一下避免处于小数res = res // i *(i - 1)return res

线性筛法求取

这个的话就是求取这个1~n这个范围的所有的欧拉数

def ouLaLiner(n):prim = [0] * (n+1)st = [False] * (n+1)cnt = 0phi = [1] * (n+1) # φ(1) = 1for i in range(2,n+1):if(not st[i]):prim[cnt] = ii+=1phi[i] = phi[i-1]j = 0while(prim[j]<=n//i):st[prim[j]*i] = Trueif(i%prim[j]==0):phi[prim[j]*i] = phi[i] *(prim[j])breakphi[prim[j]*i] = phi[i] *(prim[j]-1)j+=1 

欧拉定理

那么接下来就是这个欧拉定理,这个欧拉定理的话,可以用在我们的求逆元的时候用上。

这个定理非常简单。
在这里插入图片描述

求逆元

在这里插入图片描述

那么这里的话,求解的时候的话,还需要一个求快速幂的算法

快速幂/幂取模

def KuaiSu(a,k):res = 1while(k):if(k%2==0):res*=aa*=ak//=2return res
def KuaiSu(a,k,p):res = 1while(k):if(k%2==0):res*=a % pa*=a % pk//=2return res

原理是这个:

(a + b) % p = (a % p + b % p) % p(1)

(a - b) % p = (a % p - b % p ) % p (2)

(a * b) % p = (a % p * b % p) % p .(3)

欧几里得算法

求最小公约数

这里的话主要是这个欧几里得算法,这个欧几里得算法的话作用还是非常大的,一个是求取最小公约数,然后的话就是用拓展欧几里得算法来求取这个同余方程(当然这块是先用裴蜀定理可以证明一下)

def gcd(a,b):if(b==0):return areturn (b,a%b)

拓展欧几里得算法

在这里插入图片描述
我们使用这个拓展欧几里得算法的话可以求出这个来。
我们先来直接看到代码:

globe x=0,y=0
def exgcd(a,b,x,y):if(b == 0):x = 1,y = 0return ad = exgcd(b, a % b, y, x);y -= (a//b) * x;return d

这里的话这个y 是这样的:
在这里插入图片描述

求解同余方程

那么这个拓展欧几里得算法的话就可以去求解同余方程以及我们刚刚的求逆元。

因为我们那个求逆元其实也就是解一个同余方程,只是那个方程比较特殊而已。

为什么可以怎么来的如下:
在这里插入图片描述
这里的话就不给代码了,上面有。然后求逆的话是这样的:
在这里插入图片描述

相关文章:

Python版本的常见模板(二) 数论(一)

文章目录前言质数相关质数判断求约数求取区间质数埃氏筛法线性筛法分解质因数欧拉欧拉函数求取单个数线性筛法求取欧拉定理求逆元快速幂/幂取模欧几里得算法求最小公约数拓展欧几里得算法求解同余方程前言 本文主要是提供Python版本的常见的一些与数论相关的模板&#xff0c;例…...

SQL快速上手(知识点总结+训练资料)

文章目录一 SQL训练资料二 SQL知识点总结1.SQL语句的执行顺序2.窗口函数3.字符串处理函数模糊查询三 SQL题目的总结一 SQL训练资料 牛客SQL题目 猴子数据分析题目 关注的公众号 猴子数据分析 二 SQL知识点总结 1.SQL语句的执行顺序 每一个子句产生的中间结果供接下来的子句…...

无需经验的steam搬砖,每天操作1小时,轻松创业赚钱!

我作为一个95后社畜&#xff0c;就喜欢倒腾各种赚钱的事情&#xff0c;8年老韭菜告诉你&#xff0c;副业创收一点都不难&#xff0c;难就难在是否找对项目&#xff0c;俗话说方向不对&#xff0c;努力白费&#xff01; 什么做苦力、技能、直播卖货&#xff0c;电商等等对比我这…...

如何创建你的公司的FAQ页面?

很多企业考虑为公司搭建一个“常见问题”页面&#xff0c;作为帮助客户回答关于产品和服务的常见问题的一种方式。 FAQ页面和登录/销售页面不同&#xff0c;没有展现出直接的投资回报&#xff0c;但是为团队节省了其他成本&#xff0c;据了解&#xff0c;高达67%的客户相比于跟…...

CK-GW06-E03与欧姆龙PLC配置指南

CK-GW06-E03与欧姆龙PLC配置指南CK-GW06-E03是一款支持标准工业EtherCAT协议的网关控制器,方便用户集成到PLC等控制系统中。本控制器提供了网络 POE 供电和直流电源供电两种方式&#xff0c;确保用户在使用无POE供电功能的交换机时可采用外接电源供电&#xff1b;系统还集成了六…...

使用docker-compose部署RocketMQ5.0

简介&#xff1a;使用docker-compose部署rocketmq5.0。文中会介绍docker-compose版本以及需要注意的项第一步&#xff1a;进入hub.docker.com搜索rocketmq我们选择第一个&#xff0c;因为第一个是7个月前更新的&#xff0c;&#xff08;我看有很多博客使用的依旧是最下面的那种…...

嵌入式ARM设计编程(四) ARM启动过程控制

文章和代码已归档至【Github仓库&#xff1a;hardware-tutorial】&#xff0c;需要的朋友们自取。或者公众号【AIShareLab】回复 嵌入式 也可获取。 一、实验目的 &#xff08;1&#xff09; 掌握建立基本完整的ARM 工程&#xff0c;包含启动代码&#xff0c;C语言程序等&…...

企业维基都说好,今天我们来看看 wiki 软件的缺点有哪些?

企业维基企业wiki和内部知识库可能看起来是一回事——但它们实际上是非常不同的软件类型。也许您可能不知道你在寻找的是知识基础软件&#xff0c;还是wiki软件。 无论哪种方式&#xff0c;缺乏知识都是生产力的巨大瓶颈。事实上&#xff0c;未能分享知识是财富500强企业每年亏…...

08- 汽车产品聚类分析综合项目 (机器学习聚类算法) (项目八)

找出性价比较高的车 LabelEncoder: python:sklearn标签编码(LabelEncoder) sklearn.preprocessing.LabelEncoder的使用&#xff1a;在训练模型之前&#xff0c;通常都要对数据进行一定得处理。将类别编号是一种常用的处理方法&#xff0c;比如把类别“电脑”&#xff0c;“手机…...

揭开苹果供应链,如何将其命运与中国深度捆绑

前 言 诺基亚在2007年时拥有9亿用户&#xff0c;在手机市场上占据主导地位&#xff0c;福布斯在当时以“谁能赶上手机之王&#xff1f;”为标题刊登了一篇关于该公司的报道&#xff0c;与此同时&#xff0c;苹果公司推出了iPhone系列产品。16年后&#xff0c;苹果公司以充足的…...

Mybatis 之useGeneratedKeys注意点

一.例子 Order.javapublic class Order {private Long id;private String serial; }orderMapper.xml<?xml version"1.0" encoding"UTF-8"?> <!DOCTYPE mapper PUBLIC "-//mybatis.org/DTD Mapper 3.0" "http://mybatis.org/dtd…...

数据结构---时间复杂度

专栏&#xff1a;数据结构 个人主页&#xff1a;HaiFan. 专栏简介&#xff1a;开学数据结构&#xff0c;接下来会慢慢坑新数据结构的内容&#xff01;&#xff01;&#xff01;&#xff01; 时间复杂度前言1.算法效率1.1如何衡量一个算法的好坏1.2算法的复杂度2.时间复杂度2.1大…...

如何保证集合是线程安全的 ConcurrentHashMap如何实现高效地线程安全?

第10讲 | 如何保证集合是线程安全的? ConcurrentHashMap如何实现高效地线程安全&#xff1f; 我在之前两讲介绍了 Java 集合框架的典型容器类&#xff0c;它们绝大部分都不是线程安全的&#xff0c;仅有的线程安全实现&#xff0c;比如 Vector、Stack&#xff0c;在性能方面也…...

C++对象模型和this指针

成员变量和成员函数分开存储&#xff1a;基本概念&#xff1a;在C中&#xff0c;类内的成员变量和成员函数分开存储只有非静态成员变量才属于类的对象上每个空对象都会有一个独一无二的内存地址&#xff0c;所以&#xff0c;空对象占用内存空间的大小为1代码实现&#xff1a;#i…...

kubernetes教程 --Pod调度

Pod调度 在默认情况下&#xff0c;一个Pod在哪个Node节点上运行&#xff0c;是由Scheduler组件采用相应的算法计算出来的&#xff0c;这个过程是不受人工控制的。但是在实际使用中&#xff0c;这并不满足的需求&#xff0c;因为很多情况下&#xff0c;我们想控制某些Pod到达某…...

功率放大器科普知识(晶体管功率放大器的注意事项)

虽然功率放大器是电子实验室的常用仪器&#xff0c;但是很多人对于它却没有清晰的认识&#xff0c;下面就让安泰电子来为大家介绍功率放大器的科普内容以及使用注意事项&#xff0c;希望大家可以对功率放大器有清晰的认识。功率放大器可以把输入信号的功率放大&#xff0c;以满…...

CentOS 7转化系统为阿里龙蜥Anolis OS 7

转载&#xff1a;原社区CentOS 7迁移Anolis OS 7迁移手册 一、注意事项 Anolis OS 7生态上和依赖管理上保持跟CentOS7.x兼容&#xff0c;一键式迁移脚本centos2anolis.py&#xff0c;实现CentOS7.x到Anolis OS 7的平滑迁移。 使用迁移脚本前需要注意如下事项&#xff1a; 迁…...

【快速复习】一文看懂 Mysql 核心存储 隔离级别 锁 MVCC 机制

一文看懂 Mysql 核心存储 & 隔离级别 & 锁 & MVCC 机制 Mysql InnoDB 引擎下核心存储 数据&索引存储 IBD 文件 mysql 实际存储采用 B 树结构。 B 树是一种多路搜索树&#xff0c;其搜索性能高于 B 树 所有叶节点在同一深度&#xff0c;保证搜索效率仅叶节…...

面试题----集合

概述 从上图可以看出&#xff0c;在Java 中除了以 Map 结尾的类之外&#xff0c; 其他类都实现了 Collection 接⼝。 并且&#xff0c;以 Map 结尾的类都实现了 Map 接⼝List,Set,Map List (对付顺序的好帮⼿)&#xff1a; 存储的元素是有序的、可重复的。 Set (注重独⼀⽆⼆…...

XSS注入基础入门篇

XSS注入基础入门篇1.XSS基础概念2. XSS的分类以及示例2.1 反射型XSS2.1.1 示例1&#xff1a;dvwa low 级别的反射型XSS2.1.2 攻击流程2.2 DOM型XSS2.2.1 示例2&#xff1a;DOM型XSS注入1.环境部署2.基础版本3.进阶绕过2.3 存储型XSS2.3.1 示例1&#xff1a;dvwa low示例2.3.2 攻…...

刷题 - 数据结构(二)链表

1. 链表 1.1 题目&#xff1a;合并两个有序链表 链表的建立与插入&#xff1a;关键在于留出头部&#xff0c;创建迭代指针。 ListNode* head new ListNode; // 通过new 创建了一个数据类型为ListNode的数据 并把该数据的地址赋值给ListNodeListNode* p 0; // 再创建一个数据…...

用于隔离PWM的光耦合器选择和使用

光耦合器&#xff08;或光隔离器&#xff09;是一种将电路电隔离的器件&#xff0c;不仅在隔离方面非常出色&#xff0c;而且允许您连接到具有不同接地层或在不同电压电平下工作的电路。光耦合器具有“故障安全”功能&#xff0c;因为如果受到高于最大额定值的电压&#xff0c;…...

面试完阿里,字节,腾讯的测试岗,复盘以及面试总结

前段时间由于某些原因辞职了&#xff0c;最近一直在面试。面试这段时间&#xff0c;经历过不同业务类型的公司&#xff08;电商、酒店出行、金融、新能源、银行&#xff09;&#xff0c;也遇到了很多不同类型的面试官。 参加完三家大厂的面试聊聊我对面试的一些看法&#xff0…...

分享一个外贸客户案例

春节期间一个外贸人收到了客户的回复&#xff0c;但因为自己的处理方式造成了一个又一个问题&#xff0c;我们可以从中学到一些技巧和知识。“上次意大利的客人询价后&#xff0c;一直没回复&#xff08;中间有打过电话&#xff0c;对方说口语不行&#xff0c;我写过邮件跟进过…...

【Kubernetes】第二篇 - 购买阿里云 ECS 实例

一&#xff0c;前言 上一篇&#xff0c;简单介绍了 CI/CD 的概念以及 ECS 服务规划&#xff0c;搭建整套服务需要三台服务器&#xff0c;配置如下&#xff1a; ECS 配置启动服务说明2核4GJenkins Nexus Dockerci-server2核4GDocker Kubernetesk8s-master1核1GDocker Kube…...

数影周报:据传国内45亿条快递数据泄露,聆心智能完成Pre-A轮融资

本周看点&#xff1a;据传国内45亿条快递数据泄露&#xff1b;消息称微软解雇150 名云服务销售&#xff1b;消息称TikTok计划在欧洲再开两个数据中心&#xff1b;衣服长时间放购物车被淘宝客服嘲讽&#xff1b;聆心智能完成Pre-A轮融资......数据安全那些事据传国内45亿条快递数…...

Leetcode力扣秋招刷题路-0073

从0开始的秋招刷题路&#xff0c;记录下所刷每道题的题解&#xff0c;帮助自己回顾总结 73. 矩阵置零 给定一个 m x n 的矩阵&#xff0c;如果一个元素为 0 &#xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 示例 1&#xff1a; 输入&#xff1a;mat…...

遥感数字图像处理

遥感数字图像处理 来源&#xff1a;慕课北京师范大学朱文泉老师的课程 遥感应用&#xff1a;遥感制图、信息提取 短期内了解知识结构–>有选择的剖析经典算法原理–>系统化知识结构、并尝试实践应用 跳出算法&#xff08;尤其是数学公式&#xff09; 关注原理及解决问…...

深度学习常用的python函数(一)

由于我只简单的学过python和pytorch&#xff0c;其中有很多函数的操作都还是一知半解的&#xff0c;其中有些函数经常见到&#xff0c;所以就打算记录下来。 1.zip zip(*a):针对单个可迭代对象压缩成n个元组&#xff0c;元组数量n等于min(a中元素的最小长度) a [(1, 2), (3…...

2023年美国大学生数学建模A题:受干旱影响的植物群落建模详解+模型代码(一)

目录 前言 一、题目理解 背景 解析&#xff1a; 要求 二、建模 1.相关性分析 2.相关特征权重 只希望各位以后遇到建模比赛可以艾特认识一下我&#xff0c;我可以提供免费的思路和部分源码&#xff0c;以后的数模比赛只要我还有时间肯定会第一时间写出免费开源思路&…...

小型外包公司在哪找项目/短视频关键词seo优化

Yunfan REN renyunfanoutlook.com在使用ros的过程中&#xff0c;我们常常需要讲不同的功能包编译为动态链接库进行协作开发&#xff0c;然而在使用catkin_make的时候&#xff0c;ROS会按照默认的顺序对功能包进行编译。这导致了有的被依赖的包尚未被编译&#xff0c;未生成xxxC…...

个人网站建设一般流程/推介网

Vue中的v-pre指令 原理&#xff1a;让 Vue 跳过拥有该指令的行&#xff0c;不对其进行编译 &#x1f9ec; 特点&#xff1a;拥有v-pre的行写什么&#xff0c;页面呈现的就是什么 <h2 v-once>the initialization of n is {{n}}</h2> <h2 v-pre>the current …...

做棋牌网站建设/网络营销技能大赛优秀作品

为了适应我的VS2017版本&#xff0c;我这次安装的是16.2版本。按照网上的教程一点一点的安装。 安装很简单&#xff0c;基本按照提示就可以往下走了。 1. DevExpressUniversalTrialComplete 安装基本的DevExpress 2.DevExpress.Patch.exe 开始破解 3.DevExpress.Patch.vsix开始…...

姑苏网站建设/网络销售怎么才能找到客户

目录 # 前言 # I、 302状态码应用的典型场景...

色情WordPress站点/web网页模板

边工作边学习&#xff0c;是目前最上乘的方法了&#xff01; 自学&#xff0c;不行&#xff0c;您的状态不允许&#xff0c;需要有生存的收入。 然后是谋发展&#xff0c;只是边工作边学习&#xff0c;这个边工作收入低是最大的问题所在&#xff01; 以您的社会经历来说&#…...

wordpress添加html代码/外包推广服务

一.HTTP请求/响应 的抓包结果分析 以下是点击浏览器程序的请求 1.首行: [方法] [url] [版本] 2.Header: 请求的属性, 冒号分割的键值对;每组属性之间使用\n分隔;遇到空行表示Header部 分结束 3.空行 3.Body: 空行后面的内容都是Body. Body允许为空字符串. 如果Body存在, 则在…...