关键词：
在上一次总结过后鸽了没多久其实是快要开学赶紧来肝上两篇
今日内容——同余方程和扩展欧几里得算法
同余
同余的定义：若存在两个整数a，b，使得(a - b) MOD P为0，则称作a与b在MOD P的情况下同余
换种通俗的说法，就是，a MOD P与b MOD P相等
记作 ( aequiv b (mod P) )
对于整数a，b，c和自然数m，n
同余具有以下性质：
- 自反性：( aequiv a (mod P) )
- 对称性：若存在( aequiv b (mod P) ) ，则 ( bequiv a (mod P) )
- 传递性：若存在( aequiv b (mod P) ) ，( bequiv c (mod P) )， 则 ( aequiv b (mod P) )
- 同加性：若( aequiv b (mod P) )，则 ( (a+c)equiv (b+c) (mod P) )
- 同乘性1：若( aequiv b (mod P) )，则 ( (a*c)equiv (b*c) (mod P) )
- 同乘性2：若( aequiv b (mod P) ) ， ( cequiv d (mod P) )，则 ( (a*c)equiv (b*d) (mod P) )
- 同幂性：若( aequiv b (mod P) )，则 ( (a^c)equiv (b^c) (mod P) )
由此，我们可以得到两条推论
- ( (a*b)mod k = (a mod k)*(b mod k) mod k )
- 若( a mod p = x ,a mod q = x，p、q互质，则a mod p*q =x )
但是，相信像我一样睿智的你也发现了一个问题，没错，同余不满足同除性，即不满足若( aequiv b (mod P) )，则 ( (a/c)equiv (b/c) (mod P) )
那么除法取模要如何解决呢，秃顶聪明绝顶的数学家也发现了这个问题，利用逆元的知识，我们就可以解决这个问题啦！
但是逆元，我决定下次再讲，其实就是鸽了（咕咕咕）
扩展欧几里得算法
欧几里得算法相信大家都已经知道了QwQ
就是求gcd的辗转相除法
不知道的可以去看我的上一篇文章（理直气壮的骗访问量QwQ）
那么扩展欧几里得算法是啥？（黑人问号.jpg)
扩展欧几里得算法就是利用了欧几里得算法中迭代的过程，使其能够求出形如( ax + by = gcd(a , b) ) 的方程的应用
我们可以简单的证明和感性理解一下扩展欧几里得算法的正确性：
首先，当欧几里得算法停止迭代时
有此情况 ( a=1，b=0,此时,gcd(a,b)=x,ax+by = gcd(a,b)显然成立 )
在迭代的过程中
有 ( bx‘ + (a mod b) y‘ = gcd(b, a%b) )与 ( ax + by = gcd(a, b) )
则由上一层推出
( x= y‘ )，( y=x‘-a/b*y‘ )
于是可推至初始情况，得出解
下面给出代码的实现
int exgcd (int a, int b, int &x, int &y) if(b == 0) x = 1; y = 0; return a; int ans = exgcd ( b , a % b , x ,y ); int t = x; x = y; y= t - a / b * y; return ans;
就是这样喵
对扩展欧几里得定理的应用
利用扩展欧几里得定理，我们能够求解形如( ax+by = c )的问题
当 (c mid gcd(a,b) )时，有( ax+by = c )的不定方程有整数解
所以，把原式变形为 ( ax+by = d (d = gcd(a,b) ) )的形式，利用扩展欧几里得定理可解出方程的一组解( (x,y) )，再将其乘以 ( fracc gcd(a,b) )
就能解出原方程的解啦！（快夸我.jpg）
对扩展欧几里得定理求出解的处理
由于形如 ( ax+by = c ) 的线性不定方程有无穷多解，扩展欧几里得定理进行求解的过程中，不一定保证求出的是最小正整数解，为得到最小正整数解，我们有如下的方式
易推出，对于线性不定方程 ( ax+by = c )，有一组解(x，y) 与另一组解 ( a*(x + frac a*t gcd(a,b)) ，b*(y- frac b*t gcd(a,b) | (tin mathbbZ)) )都为原方程的解
则可得出方法：对于线性不定方程 (ax+by = c ) ，其最小正整数解为( ( x= ( (x\%t)+t)\%t) ，(t=b/gcd(a,b)))，( y=(((y\%t)+t)\%t) ，(t=a/gcd(a,b)) ) )
至此，问题得到了解决
《夜深人静写算法》数论篇-(11)线性同余
前言 上个章节简单介绍了扩展欧几里得定理，那么这个章节我们就来简述一下如何通过这个定理求解线性同余方程。一、线性同余方程 线性同余方程（也叫模线性方程）是最基本的同余方程，即ax≡b(mod n)ax\... 查看详情
《夜深人静写算法》数论篇-(11)线性同余
前言 上个章节简单介绍了扩展欧几里得定理，那么这个章节我们就来简述一下如何通过这个定理求解线性同余方程。一、线性同余方程 线性同余方程（也叫模线性方程）是最基本的同余方程，即ax≡b(mod n)ax\... 查看详情
《夜深人静写算法》数论篇-(10)扩展欧几里得定理
前言 通过扩展欧几里得定理，利用扩展欧几里得算法，可以求解线性同余方程。 那么什么是线性同余方程？什么是扩展欧几里得定理？什么是扩展欧几里得算法？接下来的几篇文章会来讲解一下这几个概念。一... 查看详情
数论扩展欧几里得算法
扩展欧几里得 上回刚写完欧几里得，那现在还有一个东西叫拓展欧几里得： 扩展欧几里得法是一个在求解同余方程等问题上的一个很好的方法，其具体功能如下： 在已知(a,b)时，求解一组(p,q)使得p*a+q*b=... 查看详情
数论逆元求解（扩展欧几里得算法+费马小定理）
看数论看得头皮发麻，o(╥﹏╥)o，总算理解了一些东西。（推荐一个dalao博客，个人感觉他的博客易懂点，可能是那些颜文字的作用（逃...））在看逆元之前我们先来看个同余方程的定理吧 同余定理：a和b取余p得到相同的余... 查看详情
扩展欧几里得(exgcd)与同余详解(代码片段)
exgcd入门以及同余基础gcd，欧几里得的智慧结晶，信息竞赛的重要算法，数论的...（编不下去了讲exgcd之前，我们先普及一下同余的性质：若，那么若，，且p1，p2互质， 有了这三个式子，就不用怕在计算时溢出了。下面我会... 查看详情
各种友(e)善(xin)数论总集（未完待续），从入门到绝望(代码片段)
目录快速幂扩展欧几里得GCD扩展欧几里得同余系列同余方程同余方程组一点想法高次同余方程BSGSexBSGS线性筛素数埃式筛欧拉筛欧拉函数讲解两道水题法雷级数可见点数原根欧拉定理原根部分性质证明（数量证不出来，一个还没... 查看详情
求解模线性方程
我曾经在数论里谈过扩展欧几里得算法只有实现，我知道它可以求模线性方程的解，但是具体也没有想过，因为同余是数论中问题现在来填下坑什么是同余给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m... 查看详情
模板01_数论_扩展欧几里得_求同余方程
题目描述求关于x的同余方程ax≡1(modb)的最小正整数解。输入输入文件为mod.in。输入只有一行，包含两个正整数a,b，用一个空格隔开。输出输出文件为mod.out。输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一... 查看详情
『线性同余方程和中国剩余定理』(代码片段)
...，则可以将方程改写为(ax+my=b)，该不定方程可以使用扩展欧几里得算法快速地求解(详见『扩展欧几里得算法ExtendedEuclid』)。对于(gcd(a,m)ot|b)的情况，也可以直接判定为原方程无解。对于使用扩展欧几里得算法求解出来的一个解(x_... 查看详情
大二博客总结第五周(代码片段)
...：1.进制转换问题2.数论板块模运算快速幂GCD和LCM扩展欧几里得算法与二元一次方程的整数解同余和逆元素数3.洛谷题解（贪心，DP，搜索）进制转换问题P1143进制转换先有n进制数转化为十进制，再由十进制... 查看详情
（数论）简单总结求逆元的几种方法
逆元(Inverseelement)，如a?b≡1(modp)，那么a，b互为模p意义下的逆元,则p|(a/c-b*c)（即a/c与b*c同余）。常用的求逆元方法有1.费马小定理 若p为素数，且gcd(a,p)=1,则a^(p-1)≡1(modp),即a*a^(p-2)≡1(modp),故a的逆元为a^p-2。2.拓展欧几里德算法... 查看详情
数论杂谈——欧几里得算法及扩展欧几里得(代码片段)
...重要的。oi中的数学，其实也就和数竞并没有什么区别。欧几里得法辗转相除法求最大公约数我们可以证明gcd(a,b)=gcd(b,a%b)，也就是我国古代数学智慧的结晶，更相损减术。并且一直递归下去，直到b的值为零，最大公约数值即为a... 查看详情
hdu1573x问题（数论--拓展欧几里德求解同余方程组的个数模版题）
题目：求在小于等于N的正整数中有多少个X满足：Xmoda[0]=b[0],Xmoda[1]=b[1],Xmoda[2]=b[2],…,Xmoda[i]=b[i],…(0<a[i]<=10)。解法：先同上题一样用拓展欧几里德求出同余方程组的最后一个方程X=ax+b，再调整x来求得X的解的个数。一... 查看详情
『扩欧简单运用』(代码片段)
扩展欧几里得算法顾名思义，扩欧就是扩展欧几里得算法，那么我们先来简单地回顾一下这个经典数论算法。对于形如(ax+by=c)的不定方程，扩展欧几里得算法可以在(O(5log_10mina,b))的时间内找到该方程的一组特解，或辅助(gcd)判断... 查看详情
poj1061青蛙的约会（数论--同余方程拓展欧几里德）
题意：已知2只青蛙的起始位置a,b和跳跃一次的距离m,n，现在它们沿着一条长度为l的纬线（圈）向相同方向跳跃。问它们何时能相遇？（好有聊的青蛙(??????‵)*）永不相遇就输出"Impossible"。（蠢得可怜-_-!）解法：用拓展欧几里德... 查看详情
poj2142thebalance数论（扩展欧几里得算法）
...问题转化为求满足方程ax+by=c，|x|+|y|的最小值。先用扩展欧几里得算法求得通解。由原方程得答案分布在y=-a/b*x+c/b（a>0,b>0,c>0），因此是k<0, 查看详情
扩展欧几里德算法的应用
...方程；（2）求解模的逆元；（3）求解模线性方程（线性同余方程）； 一、解不定方程 对于不定整数方程pa+qb=c， 1.若cmodgcd(p,q)=0,则该方程存在整数解， 查看详情