POJ1061 青蛙的约会 扩展欧几里得

模板题，这题有一点需要注意，因为要求非负，ax=b(mod L) 得保证 a>=0

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=5e4+1;
LL exgcd(LL a,LL b,LL& x,LL& y){
  if(!b){
    x=1;
    y=0;
    return a;
  }
  LL d=exgcd(b,a%b,y,x);
  y-=a/b*x;
  return d;
}
int main(){
  LL x,y,m,n,l;
  scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l);
  LL a=(m-n),b=y-x;
  if(a<0)a=-a,b=-b;
  a%=l,b%=l;
  LL d=exgcd(a,l,x,y);
  if(b%d)printf("Impossible
");
  else{
    x*=b/d;
    LL tmp=l/d;
    x=(x%tmp+tmp)%tmp;
    printf("%I64d
",x);
  } 
  return 0;
}