450
POJ1061 擴展歐幾裏得
根據題意得出的方程 (m-n)t+Lk=y-x t為步數 k為圈數 然後根據擴展歐幾裏得就能得出解 然後處理一下就可以了
對L取餘要防止負數情況
#include <iostream>
#include<cstdio>
using namespace std;
void exgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
if(b==0)
{
x=1;y=0;d=a;
return;
}
else
{
exgcd(b,a%b,d,x,y);
long long temp=x;
x=y;
y=temp-(a/b)*y;
}
}
int main()
{
long long x,y,m,n,l,gcd,ansx,ansy;
while(~scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l))
{
exgcd(m-n,l,gcd,ansx,ansy);
if((y-x)%gcd==0)
{
ansx*=(y-x)/gcd;
ansx=(ansx%l+l)%l;
printf("%d\n",ansx);
}
else
printf("Impossible\n");
}
return 0;
}
最後更新：2017-04-04 07:03:18