1477: 青蛙的约会

题目：

题解：

　　 一眼题，追及问题exgcd

　　 青蛙Rose在b点，一次跳a米。。。

　　 青蛙hanks_o在d点，一次跳c米

　　 那么YY：ax+b=cx+d (mod p) 

　　 化简：(a-c)x-p*y=d-b 

 

水代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 typedef long long LL; 8 LL exgcd(LL a,LL b,LL &x,LL &y) 9 {10     if(a==0)11     {12         x=0;y=1;13         return b;14     }15     else16     {17         LL tx,ty;18         LL d=exgcd(b%a,a,tx,ty);19         x=ty-(b/a)*tx;20         y=tx;21         return d;22     }23 }24 int main()25 {26     LL A,B,C,D,L;27     scanf("%lld%lld%lld%lld%lld",&C,&D,&A,&B,&L);28     LL a=A-B,b=-L,sum=(D-C),x,y;29     LL d=exgcd(a,b,x,y);30     if(sum%d!=0)31     {    32         printf("Impossible\n");33         return 0;34     }35     x=((x*(sum/d))%(b/d)+(b/d))%(b/d);36     printf("%lld\n",x);37     return 0;38 }