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

  • 华为手机屏幕有水印(华为手机屏幕有残影怎么解决)

    华为手机屏幕有水印(华为手机屏幕有残影怎么解决)

  • 有微信号但搜不到对方(有微信号但搜不到对方怎样加为好友)

    有微信号但搜不到对方(有微信号但搜不到对方怎样加为好友)

  • 抖音app上面能不能卖酒?(抖音的app在哪儿)

    抖音app上面能不能卖酒?(抖音的app在哪儿)

  • iphone7进水了怎么办(苹果7进水了按钮不灵了怎么办)

    iphone7进水了怎么办(苹果7进水了按钮不灵了怎么办)

  • 英特尔快速储存技术有必要开启吗(英特尔快速储存技术怎么关闭)

    英特尔快速储存技术有必要开启吗(英特尔快速储存技术怎么关闭)

  • 苹果电池保修期多久(苹果电池保修期在哪里看)

    苹果电池保修期多久(苹果电池保修期在哪里看)

  • 数据解析失败怎么回事(数据解析失败20351)

    数据解析失败怎么回事(数据解析失败20351)

  • 苹果dx开头是哪产的(苹果dx开头的序列号好不好)

    苹果dx开头是哪产的(苹果dx开头的序列号好不好)

  • 抖音小店保证金能退吗(抖音小店保证金价格表)

    抖音小店保证金能退吗(抖音小店保证金价格表)

  • 新电脑为什么那么卡(新电脑为什么那么贵)

    新电脑为什么那么卡(新电脑为什么那么贵)

  • 如何删除微信小程序游戏(如何删除微信小账本收款记录)

    如何删除微信小程序游戏(如何删除微信小账本收款记录)

  • 快手推广审核多长时间(快手推广有效果审核时间长吗)

    快手推广审核多长时间(快手推广有效果审核时间长吗)

  • ipad坏了怎么办(ipad被停用了之后怎么办)

    ipad坏了怎么办(ipad被停用了之后怎么办)

  • ps怎么选中字体(ps怎么选中字体修改)

    ps怎么选中字体(ps怎么选中字体修改)

  • 拼多多免拼在哪里找(拼多多免拼在哪点)

    拼多多免拼在哪里找(拼多多免拼在哪点)

  • 苹果怎么删除就寝时间(苹果怎样删除)

    苹果怎么删除就寝时间(苹果怎样删除)

  • 手机号怎么注销(手机号怎么注销掉)

    手机号怎么注销(手机号怎么注销掉)

  • 电脑能用手机流量上网吗(电脑用手机流量上网怎么设置)

    电脑能用手机流量上网吗(电脑用手机流量上网怎么设置)

  • creator是什么牌子(creation牌子)

    creator是什么牌子(creation牌子)

  • wps怎么发文档(wps怎么发文档给别人)

    wps怎么发文档(wps怎么发文档给别人)

  • 苹果手机碎屏怎么修(苹果手机碎屏怎么关机)

    苹果手机碎屏怎么修(苹果手机碎屏怎么关机)

  • 金山文档怎么解除绑定(金山文档怎么解除权限限制)

    金山文档怎么解除绑定(金山文档怎么解除权限限制)

  • 信号电池是什么(信号电池是什么东西)

    信号电池是什么(信号电池是什么东西)

  • python中series转dataframe的两种方法(series转换为dataframe)

    python中series转dataframe的两种方法(series转换为dataframe)

  • python中delattr可以删除对象方法(python del语法)

    python中delattr可以删除对象方法(python del语法)

  • 城镇土地使用税纳税
  • 收到的其他与筹资活动有关的现金包括
  • 配件的出口是否可以免抵退?
  • 收取不合规发票怎么处理
  • 发票大头小尾什么意思
  • 抵押车贷款会不会扣车
  • 非盈利组织捐赠支出
  • 甲供材的范围
  • 营改增后企业要交哪些税
  • 新办企业国税报税时间
  • 停车场增加收入
  • 发票管理政策
  • 红字信息表没有编号
  • 境外个人汇入汇款规定
  • 电子发票转收入怎么做为记账凭证?
  • 员工工牌的作用
  • 内部存货交易的抵消分录例题讲解
  • 华为手机屏幕有个圆点怎么取消
  • 替换重置的设备更新应考虑
  • 航天信息服务费是什么费用
  • shell检查变量是否为空
  • 计入固定资产成本的费用
  • phpshuffle
  • php递归遍历文件夹
  • 退款会退货吗
  • css水平居中和垂直居中怎么设置
  • 前端底层架构是什么意思
  • 微擎框架破解版v2.7.7
  • python操作csv
  • 个税专项扣除子女教育可以怎么扣
  • 应付票据贴现是负债吗
  • 预缴的附加税需要转出吗
  • 小规模纳税人货款怎么算
  • 房地产公司土地计入什么科目
  • phpcms怎么用
  • 关闭论坛
  • 小规模企业免征增值税如何做账
  • 错开发票所需要提供的资料和时效要求是?
  • 企业收到海河工厂发运的乙材料,并验收入库
  • 投资性房地产成本模式转公允模式差额
  • 小规模纳税人有哪些
  • 费用支出要求
  • 财政专户资金支出
  • 退回企业所得税的账务处理
  • 企业所得税的减免税额
  • 食堂菜金属于什么费用
  • 土地入账成本包括哪些
  • 新契税法商业
  • 财务报销单据粘贴视频
  • 出口退税备案完事了,为什么还没有退税勾选那个模块
  • 委托付款做账怎么做
  • 应收利息可以计提坏账准备吗
  • 工伤误工费标准是按照社平工资来算的吗
  • 外币报表折算差额会计分录
  • 企业为员工代缴社保怎样在网上申报
  • 会计每个月需要打印科目余额表吗
  • 会计成本核算方法有几种类型
  • mysql连接是什么协议
  • mysql5.7.17安装
  • mysql Community Server 5.7.19安装指南(详细)
  • 微软员工工资
  • 在windows七中
  • 安装win8.1系统步骤
  • xp系统本地用户和组在哪里
  • ttf文件安装到电脑
  • Ext JS 4实现带week(星期)的日期选择控件(实战一)
  • shell 多个文件合并
  • 安卓字库ic
  • html如何用css
  • 浅谈 vue 中的 watcher
  • javascript编写
  • node.js操作
  • unity的spine动画切换
  • unity 120帧
  • 如何将位置信息生成二维码
  • 河北税务总局发票怎么开
  • 陕西税务局官网登录
  • 重庆地方税务局电子税务局官网
  • ca证书登录不了网厅怎么办
  • 未办理税务登记取得专票抵扣
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设