POJ 1061 青蛙绕地球约会-数论-（解一元一次同余方程+扩展欧几里得算法）

题意：两只青蛙同向跳，起点是x,y，每次分别跳m,n米，地球周长是L，求最少跳几次相遇。

分析：

把式子写好就发现是一个一元一次同余方程。用扩展欧几里得算法来求。这题很基本得会。

代码：

?

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #define INF 1000000007 using namespace std; long long x,y,m,n,l; long long a,b,c,d; long long p,q,ans; long long gcd(long long a,long long b) { if(b==0) return a; else return gcd(b,a%b); } void exgcd(long long a,long long b,long long &p,long long &q) { if(b==0){ p=1;q=0;return; } else{ // exgcd(b,a%b,p,q); //注释掉的部分也是可行的 // long long tmp=p; // p=q; // q=tmp-a/b*q; exgcd(b,a%b,q,p); q-=a/b*p; } } int main() { while(cin>>x>>y>>m>>n>>l){ a=m-n;b=l; c=y-x;d=gcd(a,b); if(c%d){ cout<
        
         
?
         
?