由題意可列出方程

x + m * s - (y + n * s) = k * l;

化簡得 ? (n-m)*s + k*l = x - y

化簡得 ? (n-m)*s = x - y (mod l);

求解一次線性方程組（百度百科）；

滿足此等式的條件 （x-y）% gcd(n-m,l) == 0

然后運用擴展歐幾里得求出s ；

poj?

#include<cstdio> #include<cstring> #include<cstdlib> __int64 s,t,temp; __int64 GCD(__int64 a,__int64 b) {if(b==0) return a;return GCD(b,a%b); } void exgcd(__int64 a,__int64 b) {if(b==0){s=1;t=0;return;}else{exgcd(b,a%b);__int64 temp=s;s=t;t=temp-(a/b)*t;} } int main() {__int64 x,y,m,n,l,a,b,r,c;while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l)!=EOF){a=n-m;b=l;c=x-y;r=GCD(a,b);if(c%r) {printf("Impossible\n");continue;}a=a/r;b=b/r;c/=r;exgcd(a,b);s=((c*s)%b+b)%b;//c*s為ax+bx=1的一個特解printf("%I64d\n",s);} }

nyoj 有幾組變態(tài)的數(shù)據(jù) 要考慮n-m < 0&& x-y<0的情況

#include<cstdio> #include<cstring> #include<cstdlib> typedef long long LL; LL s,t,temp; LL GCD(LL a,LL b) {if(b==0) return a;return GCD(b,a%b); } void exgcd(LL a,LL b) {if(b==0){s=1;t=0;return;}exgcd(b,a%b);LL temp=s;s=t;t=temp-(a/b)*t; } int main() { // freopen("input.txt","r",stdin);LL x,y,m,n,l,a,b,r,c;int t;scanf("%d",&t);while(t--){scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);a=((n-m)%l+l)%l;b=l;c=((x-y)%l+l)%l;r=GCD(a,b);if(c%r) {printf("Impossible\n");continue;}a=a/r;b=b/r;c/=r;exgcd(a,b);s=((c*s)%b+b)%b;printf("%lld\n",s);} }

總結(jié)

以上是生活随笔為你收集整理的poj-青蛙的约会（扩展欧几里得）nyoj-小柯的约会的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。