关键词：
扩展欧几里得算法
扩展欧几里得算法（扩O）能在求gcd（a，b）的同时求出丢番图方程ax+by=gcd(a, b)的解。
然而怎么求呢？我们观察gcd(a, b)=gcd(b, a%b)，所以设如下两个方程：
ax+by = gcd(a,b) = d；
bx’+(a%b)y’ = gcd(b,a%b)；
明显gcd(a,b) = gcd(b,a%b)，也就是ax+by = bx’+(a%b)y’。
为了求得x与y，我们需要保证a，b不变，所以：ax+by = bx’+(a%b)y’ = bx’+(a-[a/b]*b)y’
=ay’ + b(x’ – [a/b]y’) （[a/b]表示a/b的值向下取整。）
所以可得恒等关系： x = y’ , y = (x’ – [a/b]y’)。这样就求出了一组特解。
那么如何求全解呢？直接给出递推式：
x = x0 + (b/gcd)*t
y = y0 – (a/gcd)*t
明显，b/gcd与a/gcd是互素的，也就是说它们的gcd为1。如果它们再除以一个值，某些解可能就不是整数了。
裴蜀定理
扩O有什么卵用吗？其实它可以求线性丢番图方程（不定方程）。
对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程（称为裴蜀等式）：
ax + by = m
有解当且仅当m是d的倍数。因为ax+by=gcd（a，b）。如果m不是d的整数倍的话，m就不是整数了。而因为是丢番图方程，所以a，b，x，y都为整数。m不为整数时方程无解。
裴蜀等式有解时必然有无穷多个整数解，每组解x、y都称为裴蜀数，可用扩O求得。只要将x与y同时乘上m/gcd（a，b）就行了。
特别来说，方程 ax + by = 1 有解当且仅当整数a和b互素。（因为gcd（a，b）=1）
乘法逆元
给定一个形如ax≡1 （mod m）的关于x的方程，x即为a关于m的乘法逆元。
怎么求呢？我们把它等价一下：ax mode m = 1 mod m = 1，ax=m(-y)+1，ax+my=1。
也就是说，只要求出ax+my=1这个方程的解就行了。是不是有点熟悉？对，用扩O+裴蜀求出x，y。
（注意要满足gcd（a，m）=1）
但是明显，一道题目出给你不可能让你输出无数解，通解也不现实，一般是让你求出x最小的正整数解。那怎么办呢？
x的通解是x0+m/gcd*t，在乘法逆元情况下gcd=1，所以不用考虑。所以x的通解是x0+mt。
因为通解是x0+mt，明显最小正整数解的区间是[ 0，m），所以似乎只要让x0%m就可以找到最小解了。
可是万一x0%m是负数呢？答案是取绝对值就好了。（我也不知道为什么）
下面贴代码：（待更）
扩展欧几里得与乘法逆元(代码片段)
一。欧几里得算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。基本算法：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。递归实现：1intgcd(inta,intb)23if(b==0)4returna;5return6gcd(b,a%b);7优... 查看详情
素数定理-欧几里得算法-乘法逆元
参考技术A 素数定理给出的是估计素数个数的方法： 设π(x)是小于x的素数的个数，则 π(x)≈x/lnx ... 查看详情
数论逆元求解（扩展欧几里得算法+费马小定理）
看数论看得头皮发麻，o(╥﹏╥)o，总算理解了一些东西。（推荐一个dalao博客，个人感觉他的博客易懂点，可能是那些颜文字的作用（逃...））在看逆元之前我们先来看个同余方程的定理吧 同余定理：a和b取余p得到相同的余... 查看详情
浅谈扩展欧几里得定理（附裴蜀定理）
关于扩展欧几里得定理&nbs 查看详情
深入浅出乘法逆元(代码片段)
...的运算律 2.定义 3.求解 3.1费马小定理 3.2扩展欧几里得算法 3.3线性求解深入浅出乘法逆元模的运算律先来一波模运算律表：运算律内容交换律\((a+b)\%p=(b+a)\%p\)\((a\timesb)\%p=(b\timesa)\%p\)结合律\(((a+b)\%p+c)\%p=(a+(b+c)\%p)\%p\... 查看详情
浅谈乘法逆元(代码片段)
...imesA)就是答案了。那么我们主要求的就是(C)的逆元。扩展欧几里得版首先从最简单开始，就是一个扩展欧几里得，直接求解(A imesX+P imesY=1)就行了。inlinevoidExgcd(intA,intP,intX,intY)if(!B)X=1,Y=0;elseExgcd(P,A%P,Y,X),Y-=A/B*X;这个方法虽然时间上... 查看详情
乘法逆元求解及应用(代码片段)
...则他们互为b的逆元************************逆元算法求解扩展欧几里得既然已有同余式$ax\equiv1(\modb)$那么我们可以将其转化为$ax+by=1$可以用扩展欧几里得算法求出其最小非负整数解即为a在膜b意义下的逆元不会扩 查看详情
乘法逆元怎么计算
...a*x≡1(modp)，则x=ap-2(modp)，用快速幂可快速求之。2、扩展欧几里得我们都知道模就是余数，比如12%5=12-5*2=2，18%4=18-4*4=2。（/是程序运算中的除）那么ax≡1(modp)即ax-yp=1。把y写成+的形式就是ax+py=1，为方便理解下面我们把p写成b就是a... 查看详情
51nod1256乘法逆元(扩展欧几里得)(代码片段)
1#include<iostream>2#include<algorithm>34usingnamespacestd;5typedeflonglongLL;67//给予二整数a与b,必存在有整数x与y使得ax+by=gcd(a,b)8LLextgcd(LLa,LLb,LL&x,LL&y)9LLd=a;10if(b!=0)11d=extgcd(b,a%b, 查看详情
浅谈乘法逆元(代码片段)
...对结果%p，而计算过程中有除法运算。。）二.求解1.扩展欧几里得算法求解逆元 我们知道，a*x≡1(modp)就是a*x%p=1也就是a*x+p*y=1 而扩展欧几里得算法就是用来求线性同余方程a?x≡c ( mod b )，只不过此时c=1... 查看详情
51nod1256乘法逆元扩展欧几里得
基准时间限制：1秒空间限制：131072KB分值:0难度：基础题 给出2个数M和N(M<N)，且M与N互质，找出一个数K满足0<K<N且K*M%N=1，如果有多个满足条件的，输出最小的。Input输入2个数M,N中间用空格分隔（1<=M<N<=10^9)Output输... 查看详情
求乘法逆元模板(扩展欧几里得)
voidexgcb(LLa,LLb,LL&d,LL&x,LL&y){if(!b){d=a;x=1;y=0;return;}exgcb(b,a%b,d,y,x);y-=x*(a/b);}LLny(LLa,LLb){///求a关于b的逆元(要求a，b互质)LLd,x,y;exgcb(a,b,d,x,y);returnd==1?(x+b)%b:-1;} 查看详情
关于数论(代码片段)
...接给了个链接在这（其实是懒23333），方便自己复习吧。欧几里得算法百度百科辗转相除法求gcd与lcm使用辗转相除算出gcd后，lcm可以直接通过gcd算出，但是注意求lcm的过程可能爆int，建议使用longlonginlineintgcd(inta,intb)while(b^=a^=b^=a%=... 查看详情
扩展欧几里得求乘法逆元-手算（结尾附视频）(代码片段)
写在前面：博主是一只经过实战开发历练后投身培训事业的“小山猪”，昵称取自动画片《狮子王》中的“彭彭”，总是以乐观、积极的心态对待周边的事物。本人的技术路线从Java全栈工程师一路奔向大数据开发、... 查看详情
逆元的各种求解方式
...（不会证明，想通了补）首先a与f要互素，否则无逆元1.扩展欧几里德：扩展欧几里德算法是用来在已知a,b求解一组x，y，使它们满足贝 查看详情
同余|欧拉定理|费马小定理|扩展欧拉定理|扩展欧几里得算法
目录同余基本定理欧拉定理费马小定理扩展欧拉定理扩展欧几里得算法同余基本定理欧拉定理若a,m互质，则[a^varphileft(might)equiv1left(modmight)]应用令，，这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4，所以。计算：... 查看详情
『数论』乘法逆元(代码片段)
...用欧拉函数。当(m)为质数的时候，神奇的线性方法。扩展欧几里得算法要求(a,m)互素，存在唯一解。intextgcd(inta,intb,int&x,int&y)intd=a;if(b!=0)d=extgcd(b,a%b,y,x);y-=(a/b)*x;elsex=1;y=0;returnd;intmod_inverse(inta,intm)intx,y;extgcd(a,m,x,y);return(m+x%m)%m... 查看详情
hiho1530(乘法逆元)(扩展欧几里得)(代码片段)
#1530:分数取模时间限制:1000ms单点时限:10000ms内存限制:256MB描述给定三个正整数a、b和p，满足b和p互质。这时分数a/b除以p的余数，即a/bMODp可以定义为a×b-1MODp。 其中b-1是b的逆元，它满足1≤b-1<p且b×b-1≡1MODp，满足上述条件的b... 查看详情