首页 > 代码库 > poj 1061 同余方程+扩展欧几里得+（求最小非负整数解）
poj 1061 同余方程+扩展欧几里得+（求最小非负整数解）
题目可以转化成求关于t的同余方程的最小非负数解：
x+m*t≡y+n*t (mod L)
该方程又可以转化成：
k*L+(n-m)*t=x-y
利用扩展欧几里得可以解决这个问题：
eg：对于方程ax+by=c
设tm=gcd(a,b)
若c%tm!=0，则该方程无整数解。
否则，列出方程：
a*x0+b*y0=tm
易用extend_gcd求出x0和y0
然后最终的解就是x=x0*(c/tm)，y=y0*(c/tm)
注意：若是要求最小非负整数解？
例如求y的最小非负整数解，
令r=a/tm，则y=(y%r+r)%r;
1 #include <iostream> 2 using namespace std; 3 __int64 x,y,m,n,L; 4 5 __int64 extend_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y){ 6 if (b==0){ 7 x=1;y=0; 8 return a; 9 }10 else{11 __int64 r=extend_gcd(b,a%b,y,x);12 y=y-x*(a/b);13 return r;14 }15 }16 17 int main()18 {19 cin>>x>>y>>m>>n>>L;20 21 __int64 k,t;22 __int64 tm=extend_gcd(n-m,L,t,k);23 if ((x-y)%tm!=0)24 cout<<"Impossible"<<endl;25 else26 {27 __int64 ans=t*((x-y)/tm);28 __int64 r=L/tm;29 ans=(ans%r+r)%r; //求出最小非负整数解30 //while (ans<0) ans+=k/tm; //这样做是错的= =31 cout<<ans<<endl;32 }33 34 return 0;35 }
Reference：http://www.cnblogs.com/yueshuqiao/archive/2011/08/23/2150960.html
poj 1061 同余方程+扩展欧几里得+（求最小非负整数解）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。