关键词：
#include<cstdio> using namespace std; int x,y; int gcd(int a,int b,int &x,int &y){ if(!b){ x=1,y=0; return a; } int ret=gcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return ret; } int a,b; int main(){ scanf("%d%d",&a,&b); gcd(a,b,x,y); printf("%d",(x+b)%b); }
欧几里得gcd(a,b)=gcd(b,a%b)=......
因为ax≡1（mod b） -》ax%b=1%b=1
所以ax+by=1,因为y是整数所以加个by就相当于%b(因为%b的本质是+上y个b)，所以两个式子等价
由扩展欧几里得得 ax+by=gcd(a，b)=gcd(b,a%b)=bx+(a%b=a-a/b*b)*y=....(x,0)=x。(x是最大公约数,/是整除)
最后bx=b,(a%b)*y=0
所以得 x=1，y=0
因此递归就行了
x2=y1,y2=x1-a/b*y1(原x-整除的数*a/b=模数)
最后得到的是无数解中的一种，有可能是负的，只需要加上模数就行了
扩展欧几里得noip2012同余方程
题目描述求关于x的同余方程ax≡1(modb)的最小正整数解。输入输出格式输入格式： 输入只有一行，包含两个正整数a,b，用一个空格隔开。 输出格式： 输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证... 查看详情
『线性同余方程和中国剩余定理』(代码片段)
...，则可以将方程改写为(ax+my=b)，该不定方程可以使用扩展欧几里得算法快速地求解(详见『扩展欧几里得算法ExtendedEuclid』)。对于(gcd(a,m)ot|b)的情况，也可以直接判定为原方程无解。对于使用扩展欧几里得算法求解出来的一个解(x_... 查看详情
扩展欧几里得模板（洛谷1082同余方程noip2012提高组第二天第一题）
题目描述求关于x的同余方程ax≡1(modb)的最小正整数解。输入输出格式输入格式：输入只有一行，包含两个正整数a,b，用一个空格隔开。输出格式：输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一定有解... 查看详情
洛谷p1082同余方程
水题，扩展欧几里得求解即可错误原因：扩展欧几里得写炸#include<cstdio>#include<cmath>usingnamespacestd;typedeflonglongLL;LLx,y;LLa,b;LLexgcd(LLa,LLb){if(b==0){x=1;y=0;returna;}else{LLt1=exgcd(b,a%b),t=x;x=y;y=t-a/b*y 查看详情
同余方程
...马小定理做（赤裸裸的逆元啊）还记得exgcd是啥吗？扩展欧几里得算法，用来求解形似ax+by=gcd(a,b)一类方程的解。那和这个题有什么关系啊？这个题要求关于x的同余方程ax≡1(modb)的最小正整数解，我们把这个式子展开看一下。... 查看详情
luogup1516青蛙的约会(线性同余方程扩展欧几里德）(代码片段)
...这道题，发现扩欧快忘了。根据题意可以很快地列出线性同余方程。设跳了k次x+mkΞy+nk(modl)(m-n)kΞ-(x-y)(modl)然后化一下(m-n)k+(x-y)Ξ0(modl)也就是前面一坨是l的倍数不妨设(m-n)k+(x-y)=-tl(m-n)k+tl=-(x-y)我们要求的就是保证t<=0(因为我们设... 查看详情
数论笔记-同余(代码片段)
...一次不定方程的定义与基本性质解二元一次不定方程扩展欧几里得算法类欧几里得算法乘法逆元乘法逆元的定义与基本性质乘法逆元的求法费 查看详情
poj2115clooooops[一元线性同余方程]
...$。要想方程有解，必须满足$(a,m)midd$。 这时利用扩展欧几里得求出$ax+m 查看详情
《夜深人静写算法》数论篇-(10)扩展欧几里得定理
前言 通过扩展欧几里得定理，利用扩展欧几里得算法，可以求解线性同余方程。 那么什么是线性同余方程？什么是扩展欧几里得定理？什么是扩展欧几里得算法？接下来的几篇文章会来讲解一下这几个概念。一... 查看详情
luogup1082同余方程(代码片段)
...这个公式翻译过来就是一个不定方程ax+by=1如果了解扩展欧几里得就知道这是一道exgcd的模版题//gg说的emmm那我们先来了解一下gcd和扩展gcd吧（毕竟我本人当初也不会gcd： 又称为辗转相除法因为是求最大公约数，很好理解，就... 查看详情
《夜深人静写算法》数论篇-(11)线性同余
前言 上个章节简单介绍了扩展欧几里得定理，那么这个章节我们就来简述一下如何通过这个定理求解线性同余方程。一、线性同余方程 线性同余方程（也叫模线性方程）是最基本的同余方程，即ax≡b(mod n)ax\... 查看详情
《夜深人静写算法》数论篇-(11)线性同余
前言 上个章节简单介绍了扩展欧几里得定理，那么这个章节我们就来简述一下如何通过这个定理求解线性同余方程。一、线性同余方程 线性同余方程（也叫模线性方程）是最基本的同余方程，即ax≡b(mod n)ax\... 查看详情
wenbao与欧几里得及线性同余方程(代码片段)
扩展欧几里得：设a和b不全为0，则存在整数x和y,使得 gcd(a,b)==x*a+y*b; 求解a*x+b*y=c; 令d=gcd(a,b);若c%d==0;则有解 a*x ≡c(modb) 特解可以根据扩欧求得 通解为X=x+k*(c/d);k~[0,d-1]; 令T=b/d;最小解为( 查看详情
codevs1200noip2012—同余方程
codevs.cn/problem/1200/ (题目链接)题意：求关于x的同余方程ax≡1(modb)的最小正整数解。Solution 这道题其实就是求amodb的逆元x。所谓逆元其实很简单，记a的关于模p的逆 元为a^-1,则a^-1满足aa^-1≡1(modp)，用... 查看详情
线性同余方程
...乘以gcd(a,m)/b，得到a*x0+m*y0=gcd(a,m)。这个方程可以用扩展欧几里得算法求得得到x0。等式是怎么乘的，就再把它除回来，也就是x=x0*b/gcd(a,m)。关于方程的通解，a*x+k*lcm( 查看详情
noip2012同余方程-拓展欧几里得
题目描述求关于x的同余方程ax≡1(modb)的最小正整数解。输入输出格式输入格式：输入只有一行，包含两个正整数a,b，用一个空格隔开。输出格式：输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一定有解。&nb... 查看详情
扩展欧几里德算法的应用
...方程；（2）求解模的逆元；（3）求解模线性方程（线性同余方程）； 一、解不定方程 对于不定整数方程pa+qb=c， 1.若cmodgcd(p,q)=0,则该方程存在整数解， 查看详情
noip2012day2
tags:扩展欧几里得二分答案查分倍增二分答案贪心NOIPcategories:信息学竞赛总结同余方程借教室疫情控制同余方程Solution 首先同余式可以转化为等式.\[ax\equiv1\modb\Leftrightarrowax+by=1\] 根据扩展欧几里得定理,对于式\[ax+by=k(a,b),k\... 查看详情