位置: IT常识 - 正文

数论笔记(数论电子书下载)

编辑:rootadmin
♠ use C++11 ♠ tip: 函数内必须是用变量来传输引用形参 倍数 若 $a,b,k \in \mathbb N$,且 $a \times k=b$,那么 $b$ 是 $a$ 的倍数,称 $a$ 整除 $b$,记作 $a \mid b$。 $

推荐整理分享数论笔记(数论电子书下载),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:数论讲解,数论ppt,数论ppt,数论笔记part2,数论笔记part2,数论讲义,数论笔记一,数论笔记part2,内容如对您有帮助,希望把文章链接给更多的朋友!

♠ use C++11♠ tip: 函数内必须是用变量来传输引用形参

倍数

若 \(a,b,k \in \mathbb N\),且 \(a \times k=b\),那么 \(b\) 是 \(a\) 的倍数,称 \(a\) 整除 \(b\),记作 \(a \mid b\)。

\([1,n]\in \mathbb N\) 中 \(x \in \mathbb N\) 的倍数有 \(\left \lfloor \dfrac{n}{x} \right \rfloor\) 个。

约数

若 \(a \mid b\),\(a,b\in\mathbb N\),那么 \(a\) 是 \(b\) 的约数。

\(a \in \mathbb N\) 的约数个数是有限的,记作 \(\operatorname d(n)\),\(\in \mathbb Z\)。

数论笔记(数论电子书下载)

快速算一个序列的 \(\operatorname d(n)\):设一个计数数组对应每个数,初始为 0,从左到右计算每个数,对于每个倍数加 1,当整个序列计算完后,计数数组的值是其对应数字的约数个数,时间复杂度 \(\mathcal{O}(n\operatorname{log}n)\)。下面是一个例子以及代码实现:

n 1 2 3 4 5 6d(n) 0 0 0 0 0 0 start +1 +1 +1 +1 +1 +1 step 1 in number 1 0 +1 0 +1 0 +1 step 2 in number 2 0 0 +1 0 0 +1 step 3 in number 3 .....and more 1 2 2 3 2 4 endvoid approximate_number(long long *num,long long &to){for(long long i=1;i<=to;++i){for(long long j=i;j<=to;j+=i){(*(num+j))++;}}}素数

1 不是素数也不是合数。

下面是一串判断 \(n\in \mathbb N\) 是否是素数的代码,时间复杂度 \(\mathcal{O}(\sqrt n)\)。

bool is_prime(long long &n){if(n==1)return false;for(long long i=2;i<=n/i;++i){if(n%i==0)return false;}return true;}计算一个序列每个数是否是素数:朴素筛法,有较多重复判断,时间复杂度 \(\mathcal{O}(n\operatorname{log}n)\);埃式筛法,仅是素数才向后筛,优化朴素筛法,时间复杂度 \(\mathcal{O}(n\operatorname{log log}n)\),接近线性筛。最大公约数

若 \(a,b\in \mathbb N\) 且 \(k \mid a,b \in \mathbb N\),且不存在更大的 \(k\),称 \(k\) 是 \(a,b\) 的最大公约数。

快速求 \(a,b\in \mathbb N\) 的最大公约数,欧几里得定理:\(\gcd(a,b)=\gcd(b,a \bmod b)\)。

已知 \(a,b \in \mathbb N\),可找到 \(x,y \in \mathbb Z\) 使 \(ax +by=\gcd(a,b)\),若 \(ax+by=1\) 有解,则 \(a\) 和 \(b\) 互质。

扩展欧几里得,一定存在 \(x,y\in \mathbb N\) 使贝祖等式 \(ax +by=\gcd(a,b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times b + a \bmod b) x + by = \gcd(b,a\bmod b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times x + y) b +(a \bmod b)x\),可得新的方程 \(b \times x'+(a \bmod b)\times y' = \gcd(b,a\bmod b)\) 因此可得 \(\begin{cases}x'=(\left \lfloor a \div b \right \rfloor\times x+y)\\y'=x\end{cases}\),同样倒推可得特解 \(\begin{cases}x=y'\\y=x'-(\left \lfloor a \div b \right \rfloor\times y')\end{cases}\),下面是递归代码实现:

array<long long,3> exgcd(long long &a,long long &b){if(b==0){return {1,0,a};//当b=0时,等式为ax=gcd(a,0),即ax=a//得x=1,y=0}array<long long,3> ans=exgcd(b,a%b);long long temp=ans[0];ans[0]=ans[1];ans[1]=temp-a/b*ans[1];return ans;//ans[0]为x,ans[1]为y,ans[2]为gcd(a,b)}当求得贝祖等式特解 \(x_0,y_0\in \mathbb N\) 后,可得 \(x,y\in \mathbb N\) 通解,设 \(g=\gcd(a,b)\) 通解为 \(\begin{cases}x=x_0+t\times b\div g\\y = y_0- t \times a \div g\end{cases}\),推导过程:\(\begin{cases}ax+by=g\\ax_0+bx_0=g\end{cases}\)\(\Rightarrow (x-x_0)a+(y-y_0)b=0\)\(\Rightarrow (x-x_0)a=(y_0-y)b\)\(\Rightarrow (x-x_0)\dfrac{a}{g}=(y_0-y)\dfrac{b}{g}\)\(\Rightarrow \begin{cases}x-x_0=t\times \dfrac{b}{g}\\y_0-y=t \times \dfrac{a}{g}\end{cases}\)\(\Rightarrow \begin{cases} x=x_0+t\times\dfrac{b}{g}\\y=y_0-t\times\dfrac{a}{g}\end{cases}\),其中 \(x\) 的第一个解是 \(\bigg(x\bmod\dfrac{b}{g}+\dfrac{b}{g}\bigg)\bmod \dfrac{b}{g}\)。模运算

已知 \(a,b,p\in \mathbb N\),\((a+b)\bmod p=(a\bmod p+b\bmod p)\bmod p\),\((a-b)\bmod p=(a\bmod p+b\bmod p)\bmod p\),\((a\times b)\bmod p=(a \bmod p\times b\bmod p)\bmod p\)。

若需要进行除法的模运算,与普通的不同,例子:\(\dfrac{20}{10}\bmod 5=2\)\(\nRightarrow\dfrac{20 \bmod 10}{10\bmod 10}\bmod 5=0\),所以为了求 \((a\div b) \bmod p\),\(a,b,p\in\mathbb N\),需要找到 \(b\) 的乘法逆元 \(x\in\mathbb N\),将算式变成 \((a\times x)\bmod p\)。

已知 \(a,x,m\in \mathbb N\),\(ax \equiv 1\pmod p\)\(\Rightarrow ax \bmod p=1\)\(\Rightarrow ax-\left\lfloor\dfrac{ax}{p}\right\rfloor\times p=1\),称 \(x\) 是关于 \(a\) 的乘法逆元,将 \(-\left\lfloor\dfrac{ax}{p}\right\rfloor\) 用 \(y\) 替代,得 \(ax+py=1\),即找到 \(x\) 的值即可找到 \(a\) 的乘法逆元,也可知 \(a,p\) 必须要互质。

本文链接地址:https://www.jiuchutong.com/zhishi/310160.html 转载请保留说明!

上一篇:基础数据类型之数字和字符串(测验3: 基本数据类型 (第3周))

下一篇:为在线客服系统接入chatGPT(四):chatGPT接口vue网页版,可以联系上下文语境,可以实现自己的chatGPT,附代码(在线客服系统登录)

  • 完工产品成本计入什么科目
  • 非正常损失的货物,增值税做什么科目
  • 其他应收款和其他应付款可以通用吗
  • 税控盘及维护费的会计分录
  • 经济利益的流入一定是收入吗
  • 免租期房租怎么做会计分录
  • 外地预缴所得税几个点
  • 外商独资企业在分配利润时是否扣缴个税
  • 政府会计制度中累计盈余怎么计算
  • 工会经费和职工教育经费比例
  • 发票金额小于入库金额
  • 公司因担保产生损失
  • 车船税法律制度的规定什么是以每米为计税依据的
  • 建筑施工企业的分公司区域公司等较大的
  • 泡菜增值税率
  • 审计风险可控吗
  • 远程认证是什么意思
  • 进口采购交的增值税
  • 合理损耗如何计算单价?
  • 修理时换下的废品配件怎么处理?
  • 公司投资理财需要纳税吗
  • 财务管理和会计学哪个好就业
  • 记账凭证做完之后干什么
  • 小规模纳税人三万以下免税
  • 金税盘基本信息设置
  • 收到汽车报废补贴怎么做账?
  • 暂估成本后发票怎么入账
  • 传递优化的作用
  • PHP:mb_preferred_mime_name()的用法_mbstring函数
  • 收境外汇款时怎么操作
  • php stristr函数
  • 预提的奖金需要缴纳个人所得税吗
  • 投资收益结转到哪个科目
  • csdn创作激励
  • 什么是重绘和回流
  • webpack性能优化 加载
  • 微信小程序开发者工具
  • 公司迁移到外省 税务局需要注销吗
  • 企业年报网上申报入口贵州
  • PureFTP借助MySQL实现用户身份验证的操作教程
  • 以货换货怎么交印花税
  • 开发票需要填银行吗?
  • 解决问题
  • 普票是啥意思
  • 暂估和冲暂估分录
  • 工资0申报怎么报
  • 个体户如何填报工商年报资金数额
  • 公司餐费怎么入账
  • 委托代销业务的会计分录
  • 暂估入库后发票整单折扣
  • 房地产企业城建税和教育费附加怎么算
  • 民间非盈利组织会计制度核算的基础
  • 贷款转入账号
  • 虚开发票但是没有成本如何做账?
  • 考核员工的罚款计入什么
  • 高价购买股权
  • 个人发票抬头写真名吗
  • 销售部购买电脑一台分录
  • 工业企业成本占比多少合适
  • window8系统更新
  • 简述linux系统中有哪些文件类型?
  • win7文件无法删除需要权限
  • windows语音识别
  • win8.1不能关机
  • win7系统怎么设置开机启动项
  • linux命令的含义
  • 龙芯芯片组
  • cocos2d官网
  • js拖拽元素到另一个元素
  • nodejs webapp
  • 用dos命令创建用户
  • Linuxshell脚本实现自动化软件部署内容
  • 正确的解决方式
  • jquery操作
  • 安卓模拟器比手机快吗
  • u3d地形编辑贴图
  • 控制游戏类型
  • ruby元编程第二版
  • 企业医院和事业医院的区别
  • 云南省2021年退休金计发基数
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设