POJ 1061 青蛙的约会（扩展欧几里德）

题意：中文题不详述。

思路 : 设经过s步后两青蛙相遇，则必满足（x+m*s）-(y+n*s) = K*L(k = 0,1,2....)

变形得：(n-m)*s+K*L = x-y ;

另a = n-m，b = L，c = x-y，则上式变为a*s+b*k = c。于是就变成了扩展欧几里德，求解不定方程，线性同余方程。只要上式存在整数解，则这两个青蛙能相遇，否则不能。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <math.h>
 5 
 6 using namespace std ;
 7 
 8 #define LL long long
 9 
10 LL gcd(LL a,LL b)
11 {
12     return b == 0 ? a : gcd(b,a%b) ;
13 }
14 
15 void exeulid(LL a,LL b,LL &m,LL &n)
16 {
17     if(b == 0){
18         m = 1 ;
19         n = 0 ;
20         return  ;
21     }
22     exeulid(b,a%b,m,n) ;
23     LL t  = m ;
24     m = n ;
25     n = t-a/b*n ;
26 }
27 
28 int main()
29 {
30     LL x,y,l,a = 0,b,c,r,m,n,j1 = 0,j2= 0 ,t;
31     while(~scanf("%lld %lld %lld %lld %lld",&x,&y,&m,&n,&l))
32     {
33         a = n-m ;
34         b = l ;
35         c = x-y ;
36         r = gcd(a,b) ;
37         if(c % r){
38             printf("Impossible
") ;
39             continue ;
40         }
41         a /= r ;
42         b /= r ;
43         c /= r ;
44         exeulid(a,b,j1,j2) ;
45         t = c*j1/b ;
46         j1 = c*j1-t*b ;
47         if(j1 < 0)
48             if(b > 0)
49             j1 += b ;
50     printf("%lld
",j1) ;
51     }
52     return 0 ;
53 }

View Code

POJ 1061 青蛙的约会（扩展欧几里德）

相关推荐