如何将扩展欧几里得算法实现和费马小定理用于求逆
点击联系发帖人
时间：2017-06-19 01:51
除法取模与逆元/费马小定理 - 博客频道 - CSDN.NET
分类：逆元/费马小定理
对于正整数和，如果有，那么把这个同余方程中的最小正整数解叫做模的逆元。
逆元一般用扩展欧几里得算法来求得，如果为素数，那么还可以根据费马小定理得到逆元为。（都要求a和m互质）
推导过程如下(摘自博客)
这个为费马小定理，m为素数是费马小定理的前置条件。
求a/b=x(mod M）
只要M是一个素数,而且b不是M的倍数,就可以用一个逆元整数b1,通过 a/b=a*b1 (mod M)，只能来以乘换除。
费马小定理:对于素数 M 任意不是 M 的倍数的 b，都有：b ^ (M-1) = 1 (mod M)
于是可以拆成：b*b^(M-2)=1(mod M)
于是:a/b=a/b*(b * b ^ (M-2))=a*(b ^ (M-2)) (mod M)
求a/b=x(mod M)
用扩展欧几里德算法算出b1,然后计算a*b1(mod M)
exgcd(b,M,x,y); & b1=x;
当p是个质数的时候有
inv(a) = (p - p / a) * inv(p % a) % p
设x = p % a,y = p / a
于是有 x + y * a = p
(x + y * a) % p = 0
移项得 x % p = (-y) * a % p
x * inv(a) % p = (-y) % p
inv(a) = (p - y) * inv(x) % p
于是 inv(a) = (p - p / a) * inv(p % a) % p
然后一直递归到1为止，因为1的逆元就是1#include&cstdio&
typedef long long LL;
LL inv(LL t, LL p)
{//求t关于p的逆元，注意:t要小于p，最好传参前先把t%p一下
return t == 1 ? 1 : (p - p / t) * inv(p % t, p) %
int main()
while(~scanf(&%lld%lld&, &a, &p))
printf(&%lld\n&, inv(a%p, p));
它可以在O(n)的复杂度内算出n个数的逆元
#include&cstdio&
const int N = 200000 + 5;
const int MOD = (int)1e9 + 7;
int inv[N];
int init()
inv[1] = 1;
for(int i = 2; i & N; i ++)
inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
int main()
tree__water
排名：千里之外
（0）（6）（7）（0）（5）（1）（1）（4）（7）（5）（1）（2）（1）（1）（1）（8）（4）（4）（3）（0）（2）（5）（3）（2）（2）（1）（2）（1）（2）（2）（2）（2）（3）（1）（3）（8）（1）（4）（2）（6）（0）（4）（4）（2）（4）（1）（1）（2）（1）（3）（1）（1）（1）（2）（5）（22）（1）（9）（13）（1）（2）（1）（1）（1）（1）trackbacks-0
今年网络安全的一个小作业，简单用C++实现了下 有些粗糙 先放这儿吧 ^_^
算法描述 考完试再附上
&&1/**//*&&2*&文件名称：myecu.cpp&&3*&摘&要：Extend&Euclid&Algorithm&&4*&作者：ld&&5*&完成日期：25th&June,2010&&6*/&&7&&8#include&"stdafx.h"&&9#include&&iostream&&10#include&&vector&&11#include&&algorithm&&12#include&&fstream&&13#include&&math.h&&14&15using&namespace&&16&17typedef&struct&polyNode//多项式节点项&18{&19&&&&int&&20&&&&int&&21}polyN&22&23void&CreatePoly(vector&polyNode&&poly);//构造多项式&24void&SortPolyByPower(vector&polyNode&&poly);//对多项式排序，按照降幂&25vector&polyNode&&PolyAdd(vector&polyNode&p1,vector&polyNode&p2);//多项式加法&26vector&polyNode&&PolySub(vector&polyNode&p1,vector&polyNode&p2);//多项式减法&27vector&polyNode&&PolyMultiply(vector&polyNode&p1,vector&polyNode&p2);//多项式乘法&28vector&polyNode&&PolyDiv(vector&polyNode&&p1,vector&polyNode&p2);//多项式除法&29vector&polyNode&&Eculid(vector&polyNode&&p1,vector&polyNode&&p2);//扩展欧几里得算法&30&31&32void&SortPolyByPower(vector&polyNode&&poly)//OK&33{&34&&&&vector&polyNode&::iterator&iter,tmpI&35&&&&iter&=&poly.begin();&36&&&&for&(;&iter&!=&poly.end();&iter++)//按照幂数高低排序&37&&&&{&38&&&&&&&&tmpIter&=&iter&+&<span style="COLOR: #;&39&&&&&&&&int&maxPower&=&(*iter).&40&&&&&&&&for&(;&tmpIter&!=&poly.end();&tmpIter++)&41&&&&&&&&{&42&&&&&&&&&&&&if&((*tmpIter).power&&&(*iter).power)&43&&&&&&&&&&&&{&44&&&&&&&&&&&&&&&&iter_swap(iter,tmpIter);&45&&&&&&&&&&&&}&46&&&&&&&&}&&&&&47&&&&}&48&49}&50&51void&CreatePoly(vector&polyNode&&poly)//OK&52{&53&&&&static&int&itemCount&=&<span style="COLOR: #;&54&&&&cout&&"Please&input&the&itemCount&of&the&poly:"&&&55&&&&cin&&itemC&&56&&&&for&(int&t&=&<span style="COLOR: #;&t&&&itemC&t++)&57&&&&{&58&&&&&&&&static&polyNode&tmpI&59&&&&&&&&cout&&"Please&input&the&coef&and&power:"&&&60&&&&&&&&cin&&tmpItem.coef&&tmpItem.&61&&&&&&&&poly.push_back(tmpItem);&62&63&&&&}&64&&&&SortPolyByPower(poly);&65&&&&cout&&"原始多项式为："&&&66&&&&vector&polyNode&::iterator&&67&&&&for&(&iter&=&poly.begin();iter!=&poly.end();iter++)&68&&&&{&69&&&&&&&&cout&&"X^"&&(*iter).power&&"+";&70&&&&}&71&&&&cout&&&72}&73&74vector&polyNode&&PolyAdd(vector&polyNode&p1,vector&polyNode&p2)//OK&75{&76&&&&vector&polyNode&&tmpPolyA&77&&&&vector&polyNode&::iterator&iter1,iter2;&78&&&&iter1&=&p1.begin();&79&&&&iter2&=&p2.begin();&80&&&&if&(p1.size()&==&<span style="COLOR: #)&81&&&&{&82&&&&&&&&tmpPolyAdd.clear();&83&&&&&&&&tmpPolyAdd&=&p2;&84&&&&&&&&return&tmpPolyA&85&&&&}&86&&&&else&if(p2.size()&==&<span style="COLOR: #)&87&&&&{&88&&&&&&&&tmpPolyAdd.clear();&89&&&&&&&&tmpPolyAdd&=&p1;&90&&&&&&&&return&tmpPolyA&91&&&&}&92&&&&else&93&&&&{&94&&&&&&&&tmpPolyAdd.clear();&95&&&&&&&&for&(;&iter1&!=&p1.end()&&&&iter2&!=&p2.end();)&96&&&&&&&&{&97&&&&&&&&&&&&if&((*iter1).power&&&(*iter2).power)&98&&&&&&&&&&&&{&99&&&&&&&&&&&&&&&&tmpPolyAdd.push_back(*iter1);<span style="COLOR: #0&&&&&&&&&&&&&&&&iter1++;<span style="COLOR: #1&&&&&&&&&&&&}<span style="COLOR: #2&&&&&&&&&&&&else&if&((*iter1).power&==&(*iter2).power)<span style="COLOR: #3&&&&&&&&&&&&{<span style="COLOR: #4&&&&&&&&&&&&&&&&polyNode&<span style="COLOR: #5&&&&&&&&&&&&&&&&tmp.coef&=&((*iter1).coef&+&(*iter2).coef)%<span style="COLOR: #;<span style="COLOR: #6&&&&&&&&&&&&&&&&tmp.power&=&(*iter1).<span style="COLOR: #7&&&&&&&&&&&&&&&&if&(tmp.coef&!=&<span style="COLOR: #)<span style="COLOR: #8&&&&&&&&&&&&&&&&{<span style="COLOR: #9&&&&&&&&&&&&&&&&&&&&tmpPolyAdd.push_back(tmp);<span style="COLOR: #0&&&&&&&&&&&&&&&&}<span style="COLOR: #1&&&&&&&&&&&&&&&&else;<span style="COLOR: #2&&&&&&&&&&&&&&&&iter1++;<span style="COLOR: #3&&&&&&&&&&&&&&&&iter2++;<span style="COLOR: #4&&&&&&&&&&&&}<span style="COLOR: #5&&&&&&&&&&&&else&if&((*iter1).power&&&(*iter2).power)<span style="COLOR: #6&&&&&&&&&&&&{<span style="COLOR: #7&&&&&&&&&&&&&&&&tmpPolyAdd.push_back(*iter2);<span style="COLOR: #8&&&&&&&&&&&&&&&&iter2++;<span style="COLOR: #9&&&&&&&&&&&&}<span style="COLOR: #0&&&&&&&&}<span style="COLOR: #1&&&&&&&&if&(iter2&!=&p2.end())<span style="COLOR: #2&&&&&&&&{<span style="COLOR: #3&&&&&&&&&&&&for&(;iter2&!=&p2.end();iter2++)<span style="COLOR: #4&&&&&&&&&&&&{<span style="COLOR: #5&&&&&&&&&&&&&&&&tmpPolyAdd.push_back(*iter2);<span style="COLOR: #6&&&&&&&&&&&&}<span style="COLOR: #7&&&&&&&&&&&&SortPolyByPower(tmpPolyAdd);<span style="COLOR: #8&&&&&&&&&&&&return&tmpPolyA<span style="COLOR: #9&&&&&&&&}<span style="COLOR: #0&&&&&&&&else&if(iter1&!=&p1.end())<span style="COLOR: #1&&&&&&&&{<span style="COLOR: #2&&&&&&&&&&&&for&(;iter1&!=&p1.end();iter1++)<span style="COLOR: #3&&&&&&&&&&&&{<span style="COLOR: #4&&&&&&&&&&&&&&&&tmpPolyAdd.push_back(*iter1);<span style="COLOR: #5&&&&&&&&&&&&}<span style="COLOR: #6&&&&&&&&&&&&SortPolyByPower(tmpPolyAdd);<span style="COLOR: #7&&&&&&&&&&&&return&tmpPolyA<span style="COLOR: #8&&&&&&&&}<span style="COLOR: #9&&&&&&&&else&<span style="COLOR: #0&&&&&&&&{<span style="COLOR: #1&&&&&&&&&&&&SortPolyByPower(tmpPolyAdd);<span style="COLOR: #2&&&&&&&&&&&&return&tmpPolyA<span style="COLOR: #3&&&&&&&&}<span style="COLOR: #4<span style="COLOR: #5&&&&}<span style="COLOR: #6}<span style="COLOR: #7<span style="COLOR: #8vector&polyNode&&PolySub(vector&polyNode&p1,vector&polyNode&p2)//OK<span style="COLOR: #9{<span style="COLOR: #0&&&&vector&polyNode&&tmpPolyS<span style="COLOR: #1&&&&vector&polyNode&::iterator&iter1,iter2;<span style="COLOR: #2&&&&iter1&=&p1.begin();<span style="COLOR: #3&&&&iter2&=&p2.begin();<span style="COLOR: #4&&&&for&(;&iter1&!=&p1.end()&&&&iter2&!=&p2.end();)<span style="COLOR: #5&&&&{<span style="COLOR: #6&&&&&&&&if&((*iter1).power&&&(*iter2).power)<span style="COLOR: #7&&&&&&&&{<span style="COLOR: #8&&&&&&&&&&&&tmpPolySub.push_back(*iter1);<span style="COLOR: #9&&&&&&&&&&&&iter1++;<span style="COLOR: #0&&&&&&&&}<span style="COLOR: #1&&&&&&&&else&if&((*iter1).power&==&(*iter2).power)<span style="COLOR: #2&&&&&&&&{<span style="COLOR: #3&&&&&&&&&&&&polyNode&<span style="COLOR: #4&&&&&&&&&&&&tmp.coef&=&((*iter1).coef&-&(*iter2).coef)%<span style="COLOR: #;<span style="COLOR: #5&&&&&&&&&&&&tmp.power&=&(*iter1).<span style="COLOR: #6&&&&&&&&&&&&if&(tmp.coef&!=&<span style="COLOR: #)<span style="COLOR: #7&&&&&&&&&&&&{<span style="COLOR: #8&&&&&&&&&&&&&&&&tmpPolySub.push_back(tmp);<span style="COLOR: #9&&&&&&&&&&&&}<span style="COLOR: #0&&&&&&&&&&&&else;<span style="COLOR: #1<span style="COLOR: #2&&&&&&&&&&&&iter1++;<span style="COLOR: #3&&&&&&&&&&&&iter2++;<span style="COLOR: #4&&&&&&&&}<span style="COLOR: #5&&&&&&&&else&if&((*iter1).power&&&(*iter2).power)<span style="COLOR: #6&&&&&&&&{<span style="COLOR: #7&&&&&&&&&&&&tmpPolySub.push_back(*iter2);<span style="COLOR: #8&&&&&&&&&&&&iter2++;<span style="COLOR: #9&&&&&&&&}<span style="COLOR: #0&&&&}<span style="COLOR: #1&&&&if&(iter2&==&p2.end())<span style="COLOR: #2&&&&{<span style="COLOR: #3&&&&&&&&for&(;iter1&!=&p1.end();iter1++)<span style="COLOR: #4&&&&&&&&{<span style="COLOR: #5&&&&&&&&&&&&tmpPolySub.push_back(*iter1);<span style="COLOR: #6&&&&&&&&}<span style="COLOR: #7&&&&}<span style="COLOR: #8&&&&else&if(iter1&==&p1.end())<span style="COLOR: #9&&&&{<span style="COLOR: #0&&&&&&&&for&(;iter2&!=&p2.end();iter2++)<span style="COLOR: #1&&&&&&&&{<span style="COLOR: #2&&&&&&&&&&&&tmpPolySub.push_back(*iter2);<span style="COLOR: #3&&&&&&&&}<span style="COLOR: #4&&&&}<span style="COLOR: #5&&&&SortPolyByPower(tmpPolySub);<span style="COLOR: #6&&&&return&tmpPolyS<span style="COLOR: #7}<span style="COLOR: #8<span style="COLOR: #9vector&polyNode&&PolyMultiply(&vector&polyNode&p1,&vector&polyNode&p2)//OK<span style="COLOR: #0{<span style="COLOR: #1&&&&vector&polyNode&&tmpPolyM<span style="COLOR: #2&&&&tmpPolyMul.clear();<span style="COLOR: #3&&&&vector&polyNode&&itemP<span style="COLOR: #4&&&&polyNode&<span style="COLOR: #5<span style="COLOR: #6&&&&vector&polyNode&::iterator&iter1,iter2;<span style="COLOR: #7&&&&iter1&=&p1.begin();<span style="COLOR: #8&&&&iter2&=&p2.begin();<span style="COLOR: #9&&&&for&(;&iter2&!=&p2.end();&iter2++)<span style="COLOR: #0&&&&{<span style="COLOR: #1&&&&&&&&for&(;iter1&!=&p1.end();&iter1++)<span style="COLOR: #2&&&&&&&&{<span style="COLOR: #3&&&&&&&&&&&&tmp.coef&=&(*iter1).coef&*&(*iter2).<span style="COLOR: #4&&&&&&&&&&&&tmp.power&=&(*iter1).power&+&(*iter2).<span style="COLOR: #5&&&&&&&&&&&&itemPoly.push_back(tmp);<span style="COLOR: #6&&&&&&&&}<span style="COLOR: #7&&&&&&&&SortPolyByPower(itemPoly);<span style="COLOR: #8&&&&&&&&iter1&=&p1.begin();&&&&&&&&<span style="COLOR: #9&&&&&&&&tmpPolyMul&=&PolyAdd(tmpPolyMul,itemPoly);<span style="COLOR: #0&&&&&&&&itemPoly.clear();<span style="COLOR: #1&&&&}<span style="COLOR: #2&&&&SortPolyByPower(tmpPolyMul);<span style="COLOR: #3&&&&return&tmpPolyM<span style="COLOR: #4<span style="COLOR: #5}<span style="COLOR: #6<span style="COLOR: #7vector&polyNode&&PolyDiv(vector&polyNode&&p1,&vector&polyNode&p2)//OK<span style="COLOR: #8{<span style="COLOR: #9&&&&polyNode&tmpI<span style="COLOR: #0&&&&vector&polyNode&&tmpP1&=&p1;<span style="COLOR: #1&&&&vector&polyNode&&tmpP2&=&p2;<span style="COLOR: #2&&&&static&vector&polyNode&&<span style="COLOR: #3&&&&static&vector&polyNode&&<span style="COLOR: #4&&&&vector&polyNode&&tmpM<span style="COLOR: #5&&&&vector&polyNode&&tmpR<span style="COLOR: #6&&&&static&vector&polyNode&&rP<span style="COLOR: #7<span style="COLOR: #8&&&&vector&polyNode&::iterator&iter1;<span style="COLOR: #9&&&&vector&polyNode&::iterator&iter2;<span style="COLOR: #0&&&&iter1&=&tmpP1.begin();<span style="COLOR: #1&&&&iter2&=&tmpP2.begin();<span style="COLOR: #2&&&&while&((*iter1).power&&=&(*iter2).power)<span style="COLOR: #3&&&&{<span style="COLOR: #4&&&&&&&&for&(;iter2!=tmpP2.end();iter2++)<span style="COLOR: #5&&&&&&&&{<span style="COLOR: #6&&&&&&&&&&&&tmpItem.coef&=&abs((*iter1).coef&/&(*iter2).coef);<span style="COLOR: #7&&&&&&&&&&&&tmpItem.power&=&(*iter1).power&-&(*iter2).<span style="COLOR: #8&&&&&&&&&&&&tmpResult.push_back(tmpItem);<span style="COLOR: #9&&&&&&&&&&&&result.push_back(tmpItem);<span style="COLOR: #0<span style="COLOR: #1&&&&&&&&&&&&tmpMultiply&=&PolyMultiply(p2,tmpResult);<span style="COLOR: #2&&&&&&&&&&&&vector&polyNode&::iterator&tmpI<span style="COLOR: #3&&&&&&&&&&&&tmpIter&=&tmpMultiply.begin();<span style="COLOR: #4&&&&&&&&&&&&tmpResult.clear();<span style="COLOR: #5&&&&&&&&&&&&rPoly=&PolySub(tmpP1,tmpMultiply);<span style="COLOR: #6<span style="COLOR: #7&&&&&&&&&&&&p1&=&rP<span style="COLOR: #8&&&&&&&&&&&&rPoly.clear();<span style="COLOR: #9&&&&&&&&&&&&return&PolyDiv(p1,p2);<span style="COLOR: #0&&&&&&&&}<span style="COLOR: #1&&&&}<span style="COLOR: #2&&&&SortPolyByPower(result);<span style="COLOR: #3&&&&ret&=&<span style="COLOR: #4&&&&result.clear();<span style="COLOR: #5&&&&return&<span style="COLOR: #6}<span style="COLOR: #7<span style="COLOR: #8vector&polyNode&&Eculid(vector&polyNode&&mx,vector&polyNode&&bx)//OK<span style="COLOR: #9{<span style="COLOR: #0&&&&vector&polyNode&&a1x;<span style="COLOR: #1&&&&vector&polyNode&&a2x;<span style="COLOR: #2&&&&vector&polyNode&&a3x;<span style="COLOR: #3&&&&vector&polyNode&&a3<span style="COLOR: #4<span style="COLOR: #5&&&&vector&polyNode&&b1x;<span style="COLOR: #6&&&&vector&polyNode&&b2x;<span style="COLOR: #7&&&&vector&polyNode&&b3x;<span style="COLOR: #8<span style="COLOR: #9&&&&vector&polyNode&&t1x;<span style="COLOR: #0&&&&vector&polyNode&&t2x;<span style="COLOR: #1&&&&vector&polyNode&&t3x;<span style="COLOR: #2<span style="COLOR: #3&&&&vector&polyNode&&<span style="COLOR: #4&&&&vector&polyNode&&<span style="COLOR: #5&&&&vector&polyNode&&<span style="COLOR: #6&&&&vector&polyNode&::iterator&<span style="COLOR: #7<span style="COLOR: #8&&&&static&polyNode&tmpI<span style="COLOR: #9&&&&tmpItem.coef&=&<span style="COLOR: #;<span style="COLOR: #0&&&&tmpItem.power&=&<span style="COLOR: #;<span style="COLOR: #1&&&&a1x.push_back(tmpItem);<span style="COLOR: #2&&&&a3x.clear();<span style="COLOR: #3&&&&a3x&=&<span style="COLOR: #4<span style="COLOR: #5&&&&b1x.clear();<span style="COLOR: #6&&&&tmpItem.coef&=&<span style="COLOR: #;<span style="COLOR: #7&&&&tmpItem.power&=&<span style="COLOR: #;<span style="COLOR: #8&&&&b2x.push_back(tmpItem);<span style="COLOR: #9&&&&b3x&=&<span style="COLOR: #0&&&&do&<span style="COLOR: #1&&&&{<span style="COLOR: #2&&&&&&&&iter&=&b3x.begin();<span style="COLOR: #3&&&&&&&&if&(b3x.empty())<span style="COLOR: #4&&&&&&&&{<span style="COLOR: #5&&&&&&&&&&&&cout&&"No&inverse!!!"&&<span style="COLOR: #6&&&&&&&&&&&&exit(<span style="COLOR: #);<span style="COLOR: #7&&&&&&&&}<span style="COLOR: #8&&&&&&&&else&if&(b3x.size()&==&<span style="COLOR: #&&&&((*iter).coef&==&<span style="COLOR: #&&&&(*iter).power&==&<span style="COLOR: #))<span style="COLOR: #9&&&&&&&&{<span style="COLOR: #0&&&&&&&&&&&&inverse&=&b2x;<span style="COLOR: #1&&&&&&&&&&&&return&<span style="COLOR: #2&&&&&&&&}<span style="COLOR: #3&&&&&&&&a3xcp&=&a3x;<span style="COLOR: #4&&&&&&&&qx&=&PolyDiv(a3x,b3x);<span style="COLOR: #5&&&&&&&&a3x&=&a3<span style="COLOR: #6<span style="COLOR: #7&&&&&&&&t1x&=&PolySub(a1x,PolyMultiply(qx,b1x));<span style="COLOR: #8&&&&&&&&t2x&=&PolySub(a2x,PolyMultiply(qx,b2x));<span style="COLOR: #9&&&&&&&&t3x&=&PolySub(a3x,PolyMultiply(qx,b3x));<span style="COLOR: #0<span style="COLOR: #1&&&&&&&&a1x&=&b1x;<span style="COLOR: #2&&&&&&&&a2x&=&b2x;<span style="COLOR: #3&&&&&&&&a3x&=&b3x;<span style="COLOR: #4<span style="COLOR: #5&&&&&&&&b1x&=&t1x;<span style="COLOR: #6&&&&&&&&b2x&=&t2x;<span style="COLOR: #7&&&&&&&&b3x&=&t3x;<span style="COLOR: #8&&&&}&while&(<span style="COLOR: #);<span style="COLOR: #9<span style="COLOR: #0}<span style="COLOR: #1<span style="COLOR: #2<span style="COLOR: #3int&main()<span style="COLOR: #4{<span style="COLOR: #5&&&&vector&polyNode&&polynomial1;<span style="COLOR: #6&&&&vector&polyNode&&polynomial2;<span style="COLOR: #7&&&&vector&polyNode&&<span style="COLOR: #8&&&&vector&polyNode&&::iterator&<span style="COLOR: #9&&&&vector&polyNode&&r;<span style="COLOR: #0&&&&CreatePoly(polynomial1);<span style="COLOR: #1&&&&CreatePoly(polynomial2);<span style="COLOR: #2&&&&inverse&=&Eculid(polynomial1,polynomial2);<span style="COLOR: #3&&&&SortPolyByPower(inverse);<span style="COLOR: #4&&&&iter&=&inverse.begin();<span style="COLOR: #5&&&&cout&&"求得的逆为："&&<span style="COLOR: #6&&&&for&(;iter!=inverse.end();iter++)<span style="COLOR: #7&&&&{<span style="COLOR: #8&&&&&&&&cout&&"X^"&&(*iter).power&&"+"&&<span style="COLOR: #9&&&&}<span style="COLOR: #0&&&&getchar();<span style="COLOR: #1<span style="COLOR: #2}
阅读(1562)
阅读排行榜
评论排行榜数学（21）
专题（14）
１．欧几里得
最大公因数和最小公倍数
gcd(a,b)=gcd(b,a%b)
我们令c=gcd(a,b)
a%b=a-k*b=（n-m*k）*c，可知，c也是a%b的因子,
现在只需证明c是b和a%b的最大因子，用反证法：
假设gcd(b,a%b)=d&c
设b=n1*d，a%b=m1*d
可推出a=m1*d+k1*b=m1*d+k1*n1*d
从而推出gcd(a,b)=d
int gcd(int a,int b)
return b==0 ? a : gcd(b,a%b);
2.扩展欧几里得算法
扩展欧几里得定理
对于不完全为0的非负整数a，b，gcd(a, b)表示a, b的最大公约数，必定存在整数对x，y，满足a*x+b*y==gcd(a,b)。
求出整数x,y使得 a*x+b*y=gcd(a,b)
扩展欧几里得主要有三个应用：
求解不定方程
求解模的逆元
求解同余方程
由于gcd（a，b）=gcd（b，a%b）
所以b*x1+(a%b)*y1=gcd(a,b)
a%b=a-(a/b)*b
所以gcd(a,b)=b*x1+(a-(a/b)*b)*y1
=b*x1+a*y1–(a/b)*b*y1
=a*y1+b*(x1–a/b*y1)
对于我们所求的x，y使得ax+by=gcd(a,b)
y=x1–a/b*y1
int Exgcd(int a,int b,int &x,int &y)
int ans=Exgcd(b,a%b,x,y);
int temp=x;
y-temp-a/b*y;
3.乘法逆元
b*b1≡1(modc)，那么称b1为b模c的乘法逆元。
ab(modc)=a*b1(modc),条件是b1存在（或b与c互质）。
乘法逆元可以用来求解部分除法的取模问题（分母是一个整数，并且与被取模数互质）
知道了乘法逆元的用途之后关键是怎么求出乘法逆元b1的问题,由定义b*b1≡1(modc)可以设：
b*b1=k*c+1
=&b*b1-k*c=1=gcd(b,c),(因为b,c互质)
所以问题就变成了用扩展欧几里得的求b1和k的问题了，用前面的扩展欧几里得算法就可以得到
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：40447次
积分：1746
积分：1746
排名：千里之外
原创：133篇
评论：139条
(1)(5)(1)(12)(42)(2)(12)(16)(2)(11)(32)(3)(1)(1)}
分类：逆元/费马小定理
对于正整数和，如果有，那么把这个同余方程中的最小正整数解叫做模的逆元。
逆元一般用扩展欧几里得算法来求得，如果为素数，那么还可以根据费马小定理得到逆元为。（都要求a和m互质）
推导过程如下(摘自博客)
这个为费马小定理，m为素数是费马小定理的前置条件。
求a/b=x(mod M）
只要M是一个素数,而且b不是M的倍数,就可以用一个逆元整数b1,通过 a/b=a*b1 (mod M)，只能来以乘换除。
费马小定理:对于素数 M 任意不是 M 的倍数的 b，都有：b ^ (M-1) = 1 (mod M)
于是可以拆成：b*b^(M-2)=1(mod M)
于是:a/b=a/b*(b * b ^ (M-2))=a*(b ^ (M-2)) (mod M)
求a/b=x(mod M)
用扩展欧几里德算法算出b1,然后计算a*b1(mod M)
exgcd(b,M,x,y); & b1=x;
当p是个质数的时候有
inv(a) = (p - p / a) * inv(p % a) % p
设x = p % a,y = p / a
于是有 x + y * a = p
(x + y * a) % p = 0
移项得 x % p = (-y) * a % p
x * inv(a) % p = (-y) % p
inv(a) = (p - y) * inv(x) % p
于是 inv(a) = (p - p / a) * inv(p % a) % p
然后一直递归到1为止，因为1的逆元就是1#include&cstdio&
typedef long long LL;
LL inv(LL t, LL p)
{//求t关于p的逆元，注意:t要小于p，最好传参前先把t%p一下
return t == 1 ? 1 : (p - p / t) * inv(p % t, p) %
int main()
while(~scanf(&%lld%lld&, &a, &p))
printf(&%lld\n&, inv(a%p, p));
它可以在O(n)的复杂度内算出n个数的逆元
#include&cstdio&
const int N = 200000 + 5;
const int MOD = (int)1e9 + 7;
int inv[N];
int init()
inv[1] = 1;
for(int i = 2; i & N; i ++)
inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
int main()
tree__water
排名：千里之外
（0）（6）（7）（0）（5）（1）（1）（4）（7）（5）（1）（2）（1）（1）（1）（8）（4）（4）（3）（0）（2）（5）（3）（2）（2）（1）（2）（1）（2）（2）（2）（2）（3）（1）（3）（8）（1）（4）（2）（6）（0）（4）（4）（2）（4）（1）（1）（2）（1）（3）（1）（1）（1）（2）（5）（22）（1）（9）（13）（1）（2）（1）（1）（1）（1）trackbacks-0
今年网络安全的一个小作业，简单用C++实现了下 有些粗糙 先放这儿吧 ^_^
算法描述 考完试再附上
&&1/**//*&&2*&文件名称：myecu.cpp&&3*&摘&要：Extend&Euclid&Algorithm&&4*&作者：ld&&5*&完成日期：25th&June,2010&&6*/&&7&&8#include&"stdafx.h"&&9#include&&iostream&&10#include&&vector&&11#include&&algorithm&&12#include&&fstream&&13#include&&math.h&&14&15using&namespace&&16&17typedef&struct&polyNode//多项式节点项&18{&19&&&&int&&20&&&&int&&21}polyN&22&23void&CreatePoly(vector&polyNode&&poly);//构造多项式&24void&SortPolyByPower(vector&polyNode&&poly);//对多项式排序，按照降幂&25vector&polyNode&&PolyAdd(vector&polyNode&p1,vector&polyNode&p2);//多项式加法&26vector&polyNode&&PolySub(vector&polyNode&p1,vector&polyNode&p2);//多项式减法&27vector&polyNode&&PolyMultiply(vector&polyNode&p1,vector&polyNode&p2);//多项式乘法&28vector&polyNode&&PolyDiv(vector&polyNode&&p1,vector&polyNode&p2);//多项式除法&29vector&polyNode&&Eculid(vector&polyNode&&p1,vector&polyNode&&p2);//扩展欧几里得算法&30&31&32void&SortPolyByPower(vector&polyNode&&poly)//OK&33{&34&&&&vector&polyNode&::iterator&iter,tmpI&35&&&&iter&=&poly.begin();&36&&&&for&(;&iter&!=&poly.end();&iter++)//按照幂数高低排序&37&&&&{&38&&&&&&&&tmpIter&=&iter&+&<span style="COLOR: #;&39&&&&&&&&int&maxPower&=&(*iter).&40&&&&&&&&for&(;&tmpIter&!=&poly.end();&tmpIter++)&41&&&&&&&&{&42&&&&&&&&&&&&if&((*tmpIter).power&&&(*iter).power)&43&&&&&&&&&&&&{&44&&&&&&&&&&&&&&&&iter_swap(iter,tmpIter);&45&&&&&&&&&&&&}&46&&&&&&&&}&&&&&47&&&&}&48&49}&50&51void&CreatePoly(vector&polyNode&&poly)//OK&52{&53&&&&static&int&itemCount&=&<span style="COLOR: #;&54&&&&cout&&"Please&input&the&itemCount&of&the&poly:"&&&55&&&&cin&&itemC&&56&&&&for&(int&t&=&<span style="COLOR: #;&t&&&itemC&t++)&57&&&&{&58&&&&&&&&static&polyNode&tmpI&59&&&&&&&&cout&&"Please&input&the&coef&and&power:"&&&60&&&&&&&&cin&&tmpItem.coef&&tmpItem.&61&&&&&&&&poly.push_back(tmpItem);&62&63&&&&}&64&&&&SortPolyByPower(poly);&65&&&&cout&&"原始多项式为："&&&66&&&&vector&polyNode&::iterator&&67&&&&for&(&iter&=&poly.begin();iter!=&poly.end();iter++)&68&&&&{&69&&&&&&&&cout&&"X^"&&(*iter).power&&"+";&70&&&&}&71&&&&cout&&&72}&73&74vector&polyNode&&PolyAdd(vector&polyNode&p1,vector&polyNode&p2)//OK&75{&76&&&&vector&polyNode&&tmpPolyA&77&&&&vector&polyNode&::iterator&iter1,iter2;&78&&&&iter1&=&p1.begin();&79&&&&iter2&=&p2.begin();&80&&&&if&(p1.size()&==&<span style="COLOR: #)&81&&&&{&82&&&&&&&&tmpPolyAdd.clear();&83&&&&&&&&tmpPolyAdd&=&p2;&84&&&&&&&&return&tmpPolyA&85&&&&}&86&&&&else&if(p2.size()&==&<span style="COLOR: #)&87&&&&{&88&&&&&&&&tmpPolyAdd.clear();&89&&&&&&&&tmpPolyAdd&=&p1;&90&&&&&&&&return&tmpPolyA&91&&&&}&92&&&&else&93&&&&{&94&&&&&&&&tmpPolyAdd.clear();&95&&&&&&&&for&(;&iter1&!=&p1.end()&&&&iter2&!=&p2.end();)&96&&&&&&&&{&97&&&&&&&&&&&&if&((*iter1).power&&&(*iter2).power)&98&&&&&&&&&&&&{&99&&&&&&&&&&&&&&&&tmpPolyAdd.push_back(*iter1);<span style="COLOR: #0&&&&&&&&&&&&&&&&iter1++;<span style="COLOR: #1&&&&&&&&&&&&}<span style="COLOR: #2&&&&&&&&&&&&else&if&((*iter1).power&==&(*iter2).power)<span style="COLOR: #3&&&&&&&&&&&&{<span style="COLOR: #4&&&&&&&&&&&&&&&&polyNode&<span style="COLOR: #5&&&&&&&&&&&&&&&&tmp.coef&=&((*iter1).coef&+&(*iter2).coef)%<span style="COLOR: #;<span style="COLOR: #6&&&&&&&&&&&&&&&&tmp.power&=&(*iter1).<span style="COLOR: #7&&&&&&&&&&&&&&&&if&(tmp.coef&!=&<span style="COLOR: #)<span style="COLOR: #8&&&&&&&&&&&&&&&&{<span style="COLOR: #9&&&&&&&&&&&&&&&&&&&&tmpPolyAdd.push_back(tmp);<span style="COLOR: #0&&&&&&&&&&&&&&&&}<span style="COLOR: #1&&&&&&&&&&&&&&&&else;<span style="COLOR: #2&&&&&&&&&&&&&&&&iter1++;<span style="COLOR: #3&&&&&&&&&&&&&&&&iter2++;<span style="COLOR: #4&&&&&&&&&&&&}<span style="COLOR: #5&&&&&&&&&&&&else&if&((*iter1).power&&&(*iter2).power)<span style="COLOR: #6&&&&&&&&&&&&{<span style="COLOR: #7&&&&&&&&&&&&&&&&tmpPolyAdd.push_back(*iter2);<span style="COLOR: #8&&&&&&&&&&&&&&&&iter2++;<span style="COLOR: #9&&&&&&&&&&&&}<span style="COLOR: #0&&&&&&&&}<span style="COLOR: #1&&&&&&&&if&(iter2&!=&p2.end())<span style="COLOR: #2&&&&&&&&{<span style="COLOR: #3&&&&&&&&&&&&for&(;iter2&!=&p2.end();iter2++)<span style="COLOR: #4&&&&&&&&&&&&{<span style="COLOR: #5&&&&&&&&&&&&&&&&tmpPolyAdd.push_back(*iter2);<span style="COLOR: #6&&&&&&&&&&&&}<span style="COLOR: #7&&&&&&&&&&&&SortPolyByPower(tmpPolyAdd);<span style="COLOR: #8&&&&&&&&&&&&return&tmpPolyA<span style="COLOR: #9&&&&&&&&}<span style="COLOR: #0&&&&&&&&else&if(iter1&!=&p1.end())<span style="COLOR: #1&&&&&&&&{<span style="COLOR: #2&&&&&&&&&&&&for&(;iter1&!=&p1.end();iter1++)<span style="COLOR: #3&&&&&&&&&&&&{<span style="COLOR: #4&&&&&&&&&&&&&&&&tmpPolyAdd.push_back(*iter1);<span style="COLOR: #5&&&&&&&&&&&&}<span style="COLOR: #6&&&&&&&&&&&&SortPolyByPower(tmpPolyAdd);<span style="COLOR: #7&&&&&&&&&&&&return&tmpPolyA<span style="COLOR: #8&&&&&&&&}<span style="COLOR: #9&&&&&&&&else&<span style="COLOR: #0&&&&&&&&{<span style="COLOR: #1&&&&&&&&&&&&SortPolyByPower(tmpPolyAdd);<span style="COLOR: #2&&&&&&&&&&&&return&tmpPolyA<span style="COLOR: #3&&&&&&&&}<span style="COLOR: #4<span style="COLOR: #5&&&&}<span style="COLOR: #6}<span style="COLOR: #7<span style="COLOR: #8vector&polyNode&&PolySub(vector&polyNode&p1,vector&polyNode&p2)//OK<span style="COLOR: #9{<span style="COLOR: #0&&&&vector&polyNode&&tmpPolyS<span style="COLOR: #1&&&&vector&polyNode&::iterator&iter1,iter2;<span style="COLOR: #2&&&&iter1&=&p1.begin();<span style="COLOR: #3&&&&iter2&=&p2.begin();<span style="COLOR: #4&&&&for&(;&iter1&!=&p1.end()&&&&iter2&!=&p2.end();)<span style="COLOR: #5&&&&{<span style="COLOR: #6&&&&&&&&if&((*iter1).power&&&(*iter2).power)<span style="COLOR: #7&&&&&&&&{<span style="COLOR: #8&&&&&&&&&&&&tmpPolySub.push_back(*iter1);<span style="COLOR: #9&&&&&&&&&&&&iter1++;<span style="COLOR: #0&&&&&&&&}<span style="COLOR: #1&&&&&&&&else&if&((*iter1).power&==&(*iter2).power)<span style="COLOR: #2&&&&&&&&{<span style="COLOR: #3&&&&&&&&&&&&polyNode&<span style="COLOR: #4&&&&&&&&&&&&tmp.coef&=&((*iter1).coef&-&(*iter2).coef)%<span style="COLOR: #;<span style="COLOR: #5&&&&&&&&&&&&tmp.power&=&(*iter1).<span style="COLOR: #6&&&&&&&&&&&&if&(tmp.coef&!=&<span style="COLOR: #)<span style="COLOR: #7&&&&&&&&&&&&{<span style="COLOR: #8&&&&&&&&&&&&&&&&tmpPolySub.push_back(tmp);<span style="COLOR: #9&&&&&&&&&&&&}<span style="COLOR: #0&&&&&&&&&&&&else;<span style="COLOR: #1<span style="COLOR: #2&&&&&&&&&&&&iter1++;<span style="COLOR: #3&&&&&&&&&&&&iter2++;<span style="COLOR: #4&&&&&&&&}<span style="COLOR: #5&&&&&&&&else&if&((*iter1).power&&&(*iter2).power)<span style="COLOR: #6&&&&&&&&{<span style="COLOR: #7&&&&&&&&&&&&tmpPolySub.push_back(*iter2);<span style="COLOR: #8&&&&&&&&&&&&iter2++;<span style="COLOR: #9&&&&&&&&}<span style="COLOR: #0&&&&}<span style="COLOR: #1&&&&if&(iter2&==&p2.end())<span style="COLOR: #2&&&&{<span style="COLOR: #3&&&&&&&&for&(;iter1&!=&p1.end();iter1++)<span style="COLOR: #4&&&&&&&&{<span style="COLOR: #5&&&&&&&&&&&&tmpPolySub.push_back(*iter1);<span style="COLOR: #6&&&&&&&&}<span style="COLOR: #7&&&&}<span style="COLOR: #8&&&&else&if(iter1&==&p1.end())<span style="COLOR: #9&&&&{<span style="COLOR: #0&&&&&&&&for&(;iter2&!=&p2.end();iter2++)<span style="COLOR: #1&&&&&&&&{<span style="COLOR: #2&&&&&&&&&&&&tmpPolySub.push_back(*iter2);<span style="COLOR: #3&&&&&&&&}<span style="COLOR: #4&&&&}<span style="COLOR: #5&&&&SortPolyByPower(tmpPolySub);<span style="COLOR: #6&&&&return&tmpPolyS<span style="COLOR: #7}<span style="COLOR: #8<span style="COLOR: #9vector&polyNode&&PolyMultiply(&vector&polyNode&p1,&vector&polyNode&p2)//OK<span style="COLOR: #0{<span style="COLOR: #1&&&&vector&polyNode&&tmpPolyM<span style="COLOR: #2&&&&tmpPolyMul.clear();<span style="COLOR: #3&&&&vector&polyNode&&itemP<span style="COLOR: #4&&&&polyNode&<span style="COLOR: #5<span style="COLOR: #6&&&&vector&polyNode&::iterator&iter1,iter2;<span style="COLOR: #7&&&&iter1&=&p1.begin();<span style="COLOR: #8&&&&iter2&=&p2.begin();<span style="COLOR: #9&&&&for&(;&iter2&!=&p2.end();&iter2++)<span style="COLOR: #0&&&&{<span style="COLOR: #1&&&&&&&&for&(;iter1&!=&p1.end();&iter1++)<span style="COLOR: #2&&&&&&&&{<span style="COLOR: #3&&&&&&&&&&&&tmp.coef&=&(*iter1).coef&*&(*iter2).<span style="COLOR: #4&&&&&&&&&&&&tmp.power&=&(*iter1).power&+&(*iter2).<span style="COLOR: #5&&&&&&&&&&&&itemPoly.push_back(tmp);<span style="COLOR: #6&&&&&&&&}<span style="COLOR: #7&&&&&&&&SortPolyByPower(itemPoly);<span style="COLOR: #8&&&&&&&&iter1&=&p1.begin();&&&&&&&&<span style="COLOR: #9&&&&&&&&tmpPolyMul&=&PolyAdd(tmpPolyMul,itemPoly);<span style="COLOR: #0&&&&&&&&itemPoly.clear();<span style="COLOR: #1&&&&}<span style="COLOR: #2&&&&SortPolyByPower(tmpPolyMul);<span style="COLOR: #3&&&&return&tmpPolyM<span style="COLOR: #4<span style="COLOR: #5}<span style="COLOR: #6<span style="COLOR: #7vector&polyNode&&PolyDiv(vector&polyNode&&p1,&vector&polyNode&p2)//OK<span style="COLOR: #8{<span style="COLOR: #9&&&&polyNode&tmpI<span style="COLOR: #0&&&&vector&polyNode&&tmpP1&=&p1;<span style="COLOR: #1&&&&vector&polyNode&&tmpP2&=&p2;<span style="COLOR: #2&&&&static&vector&polyNode&&<span style="COLOR: #3&&&&static&vector&polyNode&&<span style="COLOR: #4&&&&vector&polyNode&&tmpM<span style="COLOR: #5&&&&vector&polyNode&&tmpR<span style="COLOR: #6&&&&static&vector&polyNode&&rP<span style="COLOR: #7<span style="COLOR: #8&&&&vector&polyNode&::iterator&iter1;<span style="COLOR: #9&&&&vector&polyNode&::iterator&iter2;<span style="COLOR: #0&&&&iter1&=&tmpP1.begin();<span style="COLOR: #1&&&&iter2&=&tmpP2.begin();<span style="COLOR: #2&&&&while&((*iter1).power&&=&(*iter2).power)<span style="COLOR: #3&&&&{<span style="COLOR: #4&&&&&&&&for&(;iter2!=tmpP2.end();iter2++)<span style="COLOR: #5&&&&&&&&{<span style="COLOR: #6&&&&&&&&&&&&tmpItem.coef&=&abs((*iter1).coef&/&(*iter2).coef);<span style="COLOR: #7&&&&&&&&&&&&tmpItem.power&=&(*iter1).power&-&(*iter2).<span style="COLOR: #8&&&&&&&&&&&&tmpResult.push_back(tmpItem);<span style="COLOR: #9&&&&&&&&&&&&result.push_back(tmpItem);<span style="COLOR: #0<span style="COLOR: #1&&&&&&&&&&&&tmpMultiply&=&PolyMultiply(p2,tmpResult);<span style="COLOR: #2&&&&&&&&&&&&vector&polyNode&::iterator&tmpI<span style="COLOR: #3&&&&&&&&&&&&tmpIter&=&tmpMultiply.begin();<span style="COLOR: #4&&&&&&&&&&&&tmpResult.clear();<span style="COLOR: #5&&&&&&&&&&&&rPoly=&PolySub(tmpP1,tmpMultiply);<span style="COLOR: #6<span style="COLOR: #7&&&&&&&&&&&&p1&=&rP<span style="COLOR: #8&&&&&&&&&&&&rPoly.clear();<span style="COLOR: #9&&&&&&&&&&&&return&PolyDiv(p1,p2);<span style="COLOR: #0&&&&&&&&}<span style="COLOR: #1&&&&}<span style="COLOR: #2&&&&SortPolyByPower(result);<span style="COLOR: #3&&&&ret&=&<span style="COLOR: #4&&&&result.clear();<span style="COLOR: #5&&&&return&<span style="COLOR: #6}<span style="COLOR: #7<span style="COLOR: #8vector&polyNode&&Eculid(vector&polyNode&&mx,vector&polyNode&&bx)//OK<span style="COLOR: #9{<span style="COLOR: #0&&&&vector&polyNode&&a1x;<span style="COLOR: #1&&&&vector&polyNode&&a2x;<span style="COLOR: #2&&&&vector&polyNode&&a3x;<span style="COLOR: #3&&&&vector&polyNode&&a3<span style="COLOR: #4<span style="COLOR: #5&&&&vector&polyNode&&b1x;<span style="COLOR: #6&&&&vector&polyNode&&b2x;<span style="COLOR: #7&&&&vector&polyNode&&b3x;<span style="COLOR: #8<span style="COLOR: #9&&&&vector&polyNode&&t1x;<span style="COLOR: #0&&&&vector&polyNode&&t2x;<span style="COLOR: #1&&&&vector&polyNode&&t3x;<span style="COLOR: #2<span style="COLOR: #3&&&&vector&polyNode&&<span style="COLOR: #4&&&&vector&polyNode&&<span style="COLOR: #5&&&&vector&polyNode&&<span style="COLOR: #6&&&&vector&polyNode&::iterator&<span style="COLOR: #7<span style="COLOR: #8&&&&static&polyNode&tmpI<span style="COLOR: #9&&&&tmpItem.coef&=&<span style="COLOR: #;<span style="COLOR: #0&&&&tmpItem.power&=&<span style="COLOR: #;<span style="COLOR: #1&&&&a1x.push_back(tmpItem);<span style="COLOR: #2&&&&a3x.clear();<span style="COLOR: #3&&&&a3x&=&<span style="COLOR: #4<span style="COLOR: #5&&&&b1x.clear();<span style="COLOR: #6&&&&tmpItem.coef&=&<span style="COLOR: #;<span style="COLOR: #7&&&&tmpItem.power&=&<span style="COLOR: #;<span style="COLOR: #8&&&&b2x.push_back(tmpItem);<span style="COLOR: #9&&&&b3x&=&<span style="COLOR: #0&&&&do&<span style="COLOR: #1&&&&{<span style="COLOR: #2&&&&&&&&iter&=&b3x.begin();<span style="COLOR: #3&&&&&&&&if&(b3x.empty())<span style="COLOR: #4&&&&&&&&{<span style="COLOR: #5&&&&&&&&&&&&cout&&"No&inverse!!!"&&<span style="COLOR: #6&&&&&&&&&&&&exit(<span style="COLOR: #);<span style="COLOR: #7&&&&&&&&}<span style="COLOR: #8&&&&&&&&else&if&(b3x.size()&==&<span style="COLOR: #&&&&((*iter).coef&==&<span style="COLOR: #&&&&(*iter).power&==&<span style="COLOR: #))<span style="COLOR: #9&&&&&&&&{<span style="COLOR: #0&&&&&&&&&&&&inverse&=&b2x;<span style="COLOR: #1&&&&&&&&&&&&return&<span style="COLOR: #2&&&&&&&&}<span style="COLOR: #3&&&&&&&&a3xcp&=&a3x;<span style="COLOR: #4&&&&&&&&qx&=&PolyDiv(a3x,b3x);<span style="COLOR: #5&&&&&&&&a3x&=&a3<span style="COLOR: #6<span style="COLOR: #7&&&&&&&&t1x&=&PolySub(a1x,PolyMultiply(qx,b1x));<span style="COLOR: #8&&&&&&&&t2x&=&PolySub(a2x,PolyMultiply(qx,b2x));<span style="COLOR: #9&&&&&&&&t3x&=&PolySub(a3x,PolyMultiply(qx,b3x));<span style="COLOR: #0<span style="COLOR: #1&&&&&&&&a1x&=&b1x;<span style="COLOR: #2&&&&&&&&a2x&=&b2x;<span style="COLOR: #3&&&&&&&&a3x&=&b3x;<span style="COLOR: #4<span style="COLOR: #5&&&&&&&&b1x&=&t1x;<span style="COLOR: #6&&&&&&&&b2x&=&t2x;<span style="COLOR: #7&&&&&&&&b3x&=&t3x;<span style="COLOR: #8&&&&}&while&(<span style="COLOR: #);<span style="COLOR: #9<span style="COLOR: #0}<span style="COLOR: #1<span style="COLOR: #2<span style="COLOR: #3int&main()<span style="COLOR: #4{<span style="COLOR: #5&&&&vector&polyNode&&polynomial1;<span style="COLOR: #6&&&&vector&polyNode&&polynomial2;<span style="COLOR: #7&&&&vector&polyNode&&<span style="COLOR: #8&&&&vector&polyNode&&::iterator&<span style="COLOR: #9&&&&vector&polyNode&&r;<span style="COLOR: #0&&&&CreatePoly(polynomial1);<span style="COLOR: #1&&&&CreatePoly(polynomial2);<span style="COLOR: #2&&&&inverse&=&Eculid(polynomial1,polynomial2);<span style="COLOR: #3&&&&SortPolyByPower(inverse);<span style="COLOR: #4&&&&iter&=&inverse.begin();<span style="COLOR: #5&&&&cout&&"求得的逆为："&&<span style="COLOR: #6&&&&for&(;iter!=inverse.end();iter++)<span style="COLOR: #7&&&&{<span style="COLOR: #8&&&&&&&&cout&&"X^"&&(*iter).power&&"+"&&<span style="COLOR: #9&&&&}<span style="COLOR: #0&&&&getchar();<span style="COLOR: #1<span style="COLOR: #2}
阅读(1562)
阅读排行榜
评论排行榜数学（21）
专题（14）
１．欧几里得
最大公因数和最小公倍数
gcd(a,b)=gcd(b,a%b)
我们令c=gcd(a,b)
a%b=a-k*b=（n-m*k）*c，可知，c也是a%b的因子,
现在只需证明c是b和a%b的最大因子，用反证法：
假设gcd(b,a%b)=d&c
设b=n1*d，a%b=m1*d
可推出a=m1*d+k1*b=m1*d+k1*n1*d
从而推出gcd(a,b)=d
int gcd(int a,int b)
return b==0 ? a : gcd(b,a%b);
2.扩展欧几里得算法
扩展欧几里得定理
对于不完全为0的非负整数a，b，gcd(a, b)表示a, b的最大公约数，必定存在整数对x，y，满足a*x+b*y==gcd(a,b)。
求出整数x,y使得 a*x+b*y=gcd(a,b)
扩展欧几里得主要有三个应用：
求解不定方程
求解模的逆元
求解同余方程
由于gcd（a，b）=gcd（b，a%b）
所以b*x1+(a%b)*y1=gcd(a,b)
a%b=a-(a/b)*b
所以gcd(a,b)=b*x1+(a-(a/b)*b)*y1
=b*x1+a*y1–(a/b)*b*y1
=a*y1+b*(x1–a/b*y1)
对于我们所求的x，y使得ax+by=gcd(a,b)
y=x1–a/b*y1
int Exgcd(int a,int b,int &x,int &y)
int ans=Exgcd(b,a%b,x,y);
int temp=x;
y-temp-a/b*y;
3.乘法逆元
b*b1≡1(modc)，那么称b1为b模c的乘法逆元。
ab(modc)=a*b1(modc),条件是b1存在（或b与c互质）。
乘法逆元可以用来求解部分除法的取模问题（分母是一个整数，并且与被取模数互质）
知道了乘法逆元的用途之后关键是怎么求出乘法逆元b1的问题,由定义b*b1≡1(modc)可以设：
b*b1=k*c+1
=&b*b1-k*c=1=gcd(b,c),(因为b,c互质)
所以问题就变成了用扩展欧几里得的求b1和k的问题了，用前面的扩展欧几里得算法就可以得到
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：40447次
积分：1746
积分：1746
排名：千里之外
原创：133篇
评论：139条
(1)(5)(1)(12)(42)(2)(12)(16)(2)(11)(32)(3)(1)(1)}
我要回帖
更多关于 扩展欧几里得算法 的文章
更多推荐
- ·在《金铲铲之战回放怎么保存》游戏中怎样下载回放录像？
- ·guitartuna rig没有声音怎么办？
- ·看不见影子的少年根据什么小说改编的悬疑电视剧剧？
- ·求歌名？ 武当山二日游最佳方案景区里地音喇叭播放的是那首歌？
- ·元尊的等级划分及各人物等级苍玄宗是第几本书？
- ·机械手和深圳注塑机机械手厂家配合操作有几个法则？
- ·安全生产对企业的意义摩擦块的企业有哪些？
- ·中国中央银行行进行放款时应注意哪些问题
- ·有什么方法能缓解新生儿肠胀气缓解方法胀胀气？
- ·阳新县龙港镇列宁小学城区小学招生怎么注册帐号？
- ·如何正确识别螺纹钢直径如何测量
- ·这哔哩哔哩自选题选什么么
- ·广州哪里有广州1500人会议场地地租赁，公司要开培训会，需要一个专
- ·我儿子户口在湖南，现在到湖北省新生儿上户口读初一，想转学去湖南读，需要办些什么
- ·存储声音还原保真的因素的数据量，由以下哪些因素决定
- ·有mcafee病毒库下载的环境下怎么运行kmspico
- ·昆山教育局网入学报名：为什么今年入学难，明年也许会更难
- ·如何将扩展欧几里得算法实现和费马小定理用于求逆
- ·过氧化氢%30氧气属于危险化学品吗化学自曝品吗
- ·如何解决9.3.3越狱后cydia源里空白cydia的空白
- ·如何写好高考语文作文文里写了英文字母
- ·请问您那全液压锚杆钻机桩机的压桩架是什么材质的？
- ·水泥电杆2014国家标准准为什么要规定水泥的凝结时间?不符合时如何处理?
- ·农村低压农村线路改造造线路沿后墙布设高度
- ·力华金相抛光机机有哪些？质量怎么样？
- ·求求助大神这是什么歌解答
- ·欠花呗怎么借款借款2万多现在叫我强制还款，怎么办
- ·重大新药创制专项查询 专项预算 自筹经费能调低吗
- ·这地打一成语是什么成语语
- ·我只有一个卵巢，之前得过甲减前十强医院，一直在吃药，最近月经一直不来，是不是病情严重了呢？好担心！求助
- ·上海第二军医大学分数线的录取线分数线大概是多少
