exgcd

定义 又名扩展欧几里得算法（辗转相除法） 是用来求 \(ax+by=gcd(a,b)\) 中未知数的算法 算法证明 拿到一组 \(a,b\) ，设 \(G=gcd(a,b)\) 目标：求出满足 \(ax+by=G（1）\) 的 \(x\) 与 \(y\) 如果 已知一组 \(x2,y2\) ，满足 ......

给定 \(a\)，\(b\)，求解 \(ax+by=gcd(a,b)\) 的整数解。 考虑递归求解: 边界： 当 \(b=0\) 时，\(gcd(a,b)=a\)，即 \(ax+by=a\)，容易找到一组特殊解 \(x=1,y=0\)。 考虑一般情况： \(ax+by=gcd(a,b)\) \(ax ......

逆元 基础运算符号 首先先介绍一下以下文章会用到的基础运算符号. \(a\equiv b\) \((mod\) \(c)\) \(:\) 读作 \(a\) 及 \(b\) 对模 \(c\) 同余.及 \(a-b \mod c = 0\) 乘法逆元的定义 \(a\) 的逆元，及一个数可以取消一个式乘上 ......

题目链接：https://codeforces.com/gym/104090/problem/A 题解： 转化一下发现只需要求满足下式的解： \[ns+\dfrac{n\times (n+1)}{2}d \equiv C(\bmod m) \]设 \(a=n,b=\dfrac{n(n+1)}{2}, ......

# 关于exgcd的总结 我们主要讨论的是$ax+by=c$ ## 1.exgcd算法 ### **1.1 关于解的存在性** 有**裴蜀定理**知，对于方程$ax+by=c$存在解的充分必要条件是：$(a,b)|c$ tips:**裴蜀定理** 如果$a,b$均为整数，则有整数$x,y$使得$ax ......

题意： 给你四个数，n,p,d,w。让你求出任意一组x，y，z，要满足下面的条件 做法： 对于第一个式子，我们可以先用exgcd求出合法的解，在他的整个解系中进行mod(k)+k再mod(k)的操作，判断x和y能否同时非负。 对于第二个式子，我们要让z非负，那么x+y要尽可能小。而还要满足第一个式子 ......

### 例题： 先看这样一道题，给定整数 $a,b$ ，求 $x,y$ 使得 $ax+by=1$。 ### 性质： #### 性质1： 这显然是一道数学题（~~废话~~），考虑将原式根据乘法分配律转换为 $\gcd(a,b)\times (\frac{a}{\gcd(a,b)}x+\frac{b}... ......

# 7.29 数论 WIP $a\equiv b\pmod p\Rightarrow \frac{a}{d}\equiv \frac{b}{d}\pmod{\frac{p}{d}},d=\gcd(a,b,p)$。 ## exGCD 1. 若 $(a,b)=1$，则 $0\leq xb\to a\bm ......

## exgcd 扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求 $ax+by=\gcd(a,b)$ 的一组可行解。 > 部分选自[OI Wiki](https://oi-wiki.org/math/number-theory/gcd/#%E6% ......