青蛙的约会

 

 

思路：

　　扩展欧几里得；

　　设青蛙们要跳k步，我们可以得出式子

　　　　m*k+a≡n*k+b(mod l)

　　　式子变形得到

　　　　　　m*k+a-n*k-b=t*l

　　　　　　(m-n)*k-t*l=b-a

　　　　然后，exgcd函数求出k

　　　　然后输出刚刚大于0的k即可

 

来，上代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;long long n,m,a1,b1,l,xx,yy;long long exgcd(long long a,long long b,long long &x,long long &y){    if(b==0)    {        x=1,y=0;        return a;    }    long long r=exgcd(b,a%b,x,y),tmp=x;    x=y,y=tmp-a/b*y;    return r;}int main(){    scanf("%lld%lld%lld%lld%lld",&a1,&b1,&m,&n,&l);    long long a=m-n,b=l,c=b1-a1;    if(a<0) a=-a,c=-c;    long long r=exgcd(a,b,xx,yy);    if(c/r*r==c)    {        xx=xx*c/r,l=l/r;        if(xx>0) xx=xx%l;        else xx=xx%l+l;        cout<