搜索结果
查询Tags标签： 同余，共有 23条记录-
数论----同余方程
《贝祖定理》 简单来说是: 整数 a,b ,gcd(a,b)=d; 则 存在x,y使ax+by=d成立 证明： 《扩展欧几里得算法》 由贝祖定理：ax+by=gcd(a,b) 则：当不断取模gcd(a,b)=......=gcd(an,0)时 an*x+b*0=gcd,而an=gcd，所以 x=1,y=任意，为了方便y=0; 设：当前层ax+by=gcd 已知下…
2022/8/23 6:23:52 人评论 次浏览 -
同余方程
太惭愧了。我把扩欧给忘了，加紧补救一下。 扩欧用来解决形如 \(ax+by=mg,g=gcd(a,b)\) 的特解 \(x,y\) 的算法。首先我们知道假如我们求出了 \(x,y\) 满足 \(ax+by=g\) ，那么必然有特解 \(x=mx,y=my\) ，于是就把问题一般化了。 考虑欧几里得辗转相除法最后肯定会有 \(a…
2022/5/10 23:02:17 人评论 次浏览 -
【Coel.做题笔记】【旁观者…】二次剩余- Cipolla 算法
题前闲语 这周末就是省选了，甚至考场就在这个机房，可惜我并没有参加的机会。 唉，今年得好好努力了！ 题目简介 给出 \(N,p\)，求解方程 \[x^2 \equiv N(\bmod ~p) \]多组数据。 保证 \(p\) 是奇素数。 输入输出格式 输入格式第一行一个整数 $T$ 表示数据组数。 接下来 …
2022/4/14 20:12:43 人评论 次浏览 -
[Acwing蓝桥杯数学知识] 扩展欧几里得线性同余方程
扩展欧几里得用于求解方程 ax+by=gcd(a,b)的解 当 b=0时 ax+by=aax+by=a 故而 x=1,y=0x=1,y=0当 b≠0 时因为gcd(a,b)=gcd(b,a%b) 而bx′+(a%b)y′=gcd(b,a%b) bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a%b)ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)故而x=y′,y=x′−⌊a/b⌋…
2022/3/31 6:23:55 人评论 次浏览 -
同余
定义： 若\((a-b)\ mod\ p=0\)，则\(a\)与\(b\)在模\(p\)的意义下同余，记作\(a\equiv b(mod\ p)\)。(\(a,c\in Z\)(整数)，\(m\in N^*\)(正整数)) 性质： 1.\(a\equiv a(mod\ p)\) 2.若\(a\equiv b(mod\ p)\)，则\(b\equiv a(mod\ p)\) 3.若\(a\equiv b(mod\ p)\)，且\(b…
2022/2/18 23:19:07 人评论 次浏览 -
数论同余学习笔记 Part 2
逆元 准确地说，这里讲的是模意义下的乘法逆元。 定义：如果有同余方程 \(ax\equiv 1\pmod p\)，则 \(x\) 称为 \(a\bmod p\) 的逆元，记作 \(a^{-1}\)。 作用是抵消乘法，即 \(x\cdot a\cdot a^{-1}\equiv x\pmod p\) 进一步可以得到 \(\frac xa\equiv x\times a^{-1}\pm…
2022/2/8 23:51:17 人评论 次浏览 -
同余方程组
由上可得两个同余方程可得一个线性方程 ，linearEquation（m1，-m2，a2-a1） 可解出y1 代回x=a1+m1y1，得：x0=a1+m1y1 ==> x=x0+k*min(m1,m2),得一个新方程： x=x0(mod min(m1,m2)) 此处涉及的是逐级合并法，最终的x的结果为上一个x关于最后两式子的m的最小公倍数的同…
2022/2/3 23:42:40 人评论 次浏览 -
《夜深人静写算法》数论篇 - (11) 线性同余
前言上个章节简单介绍了 扩展欧几里得定理，那么这个章节我们就来简述一下如何通过这个定理求解线性同余方程。一、线性同余方程线性同余方程（也叫模线性方程）是最基本的同余方程，即 a x ≡ b ( m o d n ) ax \equiv b(mod \ n) ax
2021/12/29 14:07:25 人评论 次浏览 -
《夜深人静写算法》数论篇 - (11) 线性同余
前言上个章节简单介绍了 扩展欧几里得定理，那么这个章节我们就来简述一下如何通过这个定理求解线性同余方程。一、线性同余方程线性同余方程（也叫模线性方程）是最基本的同余方程，即 a x ≡ b ( m o d n ) ax \equiv b(mod \ n) ax
2021/12/29 14:07:25 人评论 次浏览 -
《算法竞赛进阶指南》笔记
目录0x30 数学知识0x33 同余概念与定理例题The Luckiest Number扩展欧几里得算法$(exgcd)$定理及概念线性同余方程高次同余方程0x34 矩阵乘法0x35 高斯消元与线性空间高斯消元线性空间0x36 组合计数基本概念组合数的求法二项式定理多重集的排列数与组合数Lucas 定理Catala…
2021/11/15 22:12:21 人评论 次浏览 -
《算法竞赛进阶指南》笔记
目录0x30 数学知识0x33 同余概念与定理例题The Luckiest Number扩展欧几里得算法$(exgcd)$定理及概念线性同余方程高次同余方程0x34 矩阵乘法0x35 高斯消元与线性空间高斯消元线性空间0x36 组合计数基本概念组合数的求法二项式定理多重集的排列数与组合数Lucas 定理Catala…
2021/11/15 22:12:21 人评论 次浏览 -
【数论】数论算法系列文章汇总目录（持续更新中）
本文属于「数论」系列文章的汇总目录。这一系列着重于数论算法的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏本文以作备忘。此外，在本系列学习文章中，为了透彻理解数论知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在…
2021/11/5 12:39:39 人评论 次浏览 -
【数论】数论算法系列文章汇总目录（持续更新中）
本文属于「数论」系列文章的汇总目录。这一系列着重于数论算法的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏本文以作备忘。此外，在本系列学习文章中，为了透彻理解数论知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在…
2021/11/5 12:39:39 人评论 次浏览 -
高级图论
1. 同余最短路 说难也不算很难，挺有意思的一个知识点，不过应用不多。 前置知识：SPFA & Dijkstra 求最短路。 1.1. 算法简介 同余最短路常用来求解：给出 \(n\ (n\leq 50)\) 个数 \(a_i\ (1\leq a_i\leq 10^5)\)，求在某个范围（\(10^{18}\)）内有多少个数能够由这些…
2021/10/14 23:46:32 人评论 次浏览 -
高级图论
1. 同余最短路 说难也不算很难，挺有意思的一个知识点，不过应用不多。 前置知识：SPFA & Dijkstra 求最短路。 1.1. 算法简介 同余最短路常用来求解：给出 \(n\ (n\leq 50)\) 个数 \(a_i\ (1\leq a_i\leq 10^5)\)，求在某个范围（\(10^{18}\)）内有多少个数能够由这些…
2021/10/14 23:46:32 人评论 次浏览
