#include#include #define ll long longusing namespace std;ll gcd(ll a,ll b,ll &x,ll &y){ if(!b){ x=1,y=0; return a; } int ret=gcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return ret;} int main(){ll x,y;ll a,b;ll m,n,l,X,Y;ll g; scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l); if(n-m<0)swap(m,n),swap(x,y); if((x-y)%(g=gcd(n-m,l,X,Y))!=0) printf("Impossible"); else printf("%lld",((x-y)/g*X%(l/g)+(l/g))%(l/g)); }
有数学关系可得(m-n)x+(a-b)≡ 0(mod l)
即 (m-n)x+l*y=(b-a)
由扩展欧几里得得(m-n)x0+l*y0=gcd(a,b) ————两边同时乘(b-a)/gcd(a,b)!!!必须是整数&&(m-n>0)
->>(m-n)x0*(b-a)/gcd(a,b)+l*y0*(b-a)/gcd(a,b)=(b-a)
则可以用扩展欧几里得求出x0,再乘(b-a)/gcd(a,b)