数论之欧几里德算法（四）

简介：欧几里德算法的应用

题目链接：poj 1061

解题思路： A = m – n , B = y – x , N = L , 题目转化为求解模线性方程Ak ≡ B(mod N) 预处理：若m小于n，，交换m与n，x与y

代码：

;a,&x,long long &y){if(b==0){x=1,y=0;return a;}long long r=extend_gcd(b,a%b,y,x);y-=a/b*x;return r;}int main(){long long x,y,m,n,L,ans;while(~scanf(“%lld %lld %lld %lld %lld”,&x,&y,&m,&n,&L)){if(m<n){swap(x,y);swap(m,n);}long long a=m-n,b=y-x,X,Y;d=extend_gcd(a,L,X,Y);if(b%d==0){X%=L,X+=L,X%=L;ans=X*(b/d)%(L/d);}elseans=-1;if(ans==-1)printf(“Impossible\n”);elseprintf(“%lld\n”,ans);}return 0;}

最好的感觉就是你什么都跟我说。