首页 > 代码库 > POJ 1061
POJ 1061
胡乱写一下，竟然是一次同余方程的内容。
设
a=n-m; b=L; d=x-y; 得
ax+by=d
然后，根定理，方程有解必须gcd(a,b)|d。
确定有解后，两边除以gcd(a,b); 此时gcd(a‘,b‘)=1;使用EXGCD求出为1的解后再乘上d/gcd(a,b)。
但要求最小解，就尽可能的把ax的值附到by上去，所以可以有ax=b*k+a*v（因为附到by上后必须仍上a*x的形式）。两边同除a就可得到结果。其实，只有一个可能，就是a=1。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;__int64 gcd(__int64 a,__int64 b){ if(b==0) return a; return gcd(b,a%b);}void exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y){ if(b==0){ x=1; y=0; return ; } exgcd(b,a%b,x,y); __int64 t=x; x=y; y=t-a/b*y;}int main(){ __int64 x,y,m,n,L,a,b,c,d; while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L)!=EOF){ a=n-m; b=L; d=x-y; c=gcd(a,b); if(d%c!=0){ printf("Impossible\n"); continue; } a/=c; b/=c; d/=c; exgcd(a,b,x,y); x*=d; y*=d; __int64 t=(x%(b)+b)%b; printf("%I64d\n",t); } return 0;}
POJ 1061
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。