位置: 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,附代码(在线客服系统登录)

  • 租集体土地建厂合法吗
  • 基本税种有哪些税种
  • 开专票还是开普发票
  • 小规模纳税人城市维护建设税税率
  • 企业净利率多少算正常
  • 电子承兑凭证
  • 办公室租金发票可以扺军品企业增值税吗
  • 一般纳税人废业怎么办
  • 银行日记账写错了怎么改
  • 不动产折旧年限的规定
  • 国有独资企业交企业所得税规定
  • 向境外分派红利怎么计算缴纳企业所得税
  • 自创商誉企业所得税可以扣除吗
  • 会计上的未达账项是什么
  • 没有资质的建筑公司怎样接工程
  • 自然人股权转让要交什么税
  • 农产品收购发票图片
  • 拒绝税务检查的情形
  • 增值税减少在借方还是贷方
  • 金融企业三大使命是什么
  • 开模具公司要什么设备
  • 技术服务费成本票是什么
  • 金蝶标准版利润表季度怎么选
  • 广播影视服务需要交文化事业建设费吗
  • 房企的预收账款是什么
  • 如何在Windows 11上卸载更新
  • 什么是电子发票图片
  • word2013压缩图片
  • cmos电池低是什么意思
  • word要打印保存在哪个类型
  • linux系统中配置网卡ip地址的命令为
  • 任务栏变宽了怎么调回来win11
  • 微博 照片水印
  • 老大心态是什么意思
  • 新企业办理地税登记流程
  • linux tr
  • PHP:Memcached::incrementByKey()的用法_Memcached类
  • uniapp 信息推送
  • 应缴纳的房产税计入什么科目
  • php bind_result
  • 微信公众号服务平台
  • 你别找了
  • 强大的图片预览软件
  • ecshop功能
  • 财政补助收入分录
  • 固定资产售后回购会计处理
  • 报销职工福利
  • c语言fseek函数
  • 如何确定可以结婚生子
  • 固定资产清理年末余额怎么处理
  • mongodb分区分片
  • 已冲销凭证是否可以删除
  • 金税四期讲解视频
  • 国债利息收入的分录
  • 进口关税征收方法
  • 债务重组的账务处理和税收差异
  • 法人银行贷款
  • 跨年度暂估成本高了怎么办
  • 人工安装费是几个点税税率
  • 应交增值税减免税款科目
  • 应交个人所得税借方余额表示什么
  • 客运运价杂费收据填写例题
  • mysql如何实现主从复制的具体流程
  • 清除windows10登录密码
  • win7无法安装谷歌
  • 在Linux系统中安装虚拟window
  • linux怎么操作
  • cyb2k.exe是安全进程吗 cyb2k进程危险吗
  • sistray.exe - sistray是什么进程 有什么用
  • linux删除一个非空子目录命令
  • windows8中文版是什么版本
  • Node.js中的什么模块是用于处理文件和目录的
  • python 操作微信
  • js 模块 modules
  • javascript核心技术
  • python怎么自定义函数
  • 重庆车位过户需要多久时间
  • 南京江宁区地税局待遇(南京各个区税务局待遇)
  • 钢管租赁可以开建筑材料吗
  • 税务发票机器怎么操作
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设