SGU 106 The equation 扩展欧几里得好题

扩展欧几里得的应用……见算法竞赛入门经典p.179

注意两点：1.解不等式的时候除负数变号

2.各种特殊情况的判断( a=0 && b=0 && c=0 ) ( a=0 && b=0 && c!=0 ) ( a=0 && b!=0 )( a!=0 && b=0 )

能加深对扩展欧几里得的理解，不错的一题

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <algorithm>
 6 
 7 #define LL long long int
 8 
 9 using namespace std;
10 
11 void ExGcd( LL a, LL b, LL &d, LL &x, LL &y )
12 {
13     if ( !b )
14         d = a, x = 1, y = 0;
15     else
16     {
17         ExGcd( b, a % b, d, y, x );
18         y -= x * ( a / b );
19     }
20     return;
21 }
22 
23 int main()
24 {
25     LL a, b, c, x1, x2, y1, y2;
26     while ( scanf( "%I64d%I64d%I64d%I64d%I64d%I64d%I64d", &a, &b, &c, &x1, &x2, &y1, &y2 ) == 7 )
27     {
28         if ( a == 0 && b == 0 )
29         {
30             if ( c == 0 )
31                 printf( "%I64d
", (x2 - x1 + 1)*(y2 - y1 + 1) );
32             else puts("0");
33             continue;
34         }
35         if ( a == 0 )
36         {
37             if ( (-c) % b == 0 )
38             {
39                 LL y = (-c) / b;
40                 if ( y >= y1 && y <= y2 ) puts("1");
41                 else puts("0");
42             }
43             else puts("0");
44 
45             continue;
46         }
47         if ( b == 0 )
48         {
49             if ( (-c) % a == 0 )
50             {
51                 LL x = (-c) / a;
52                 if ( x >= x1 && x <= x2 ) puts("1");
53                 else puts("0");
54             }
55             else puts("0");
56             continue;
57         }
58         LL g, x0, y0;
59         ExGcd( a, b, g, x0, y0 );
60         if ( (-c) % g == 0 ) //如果有解
61         {
62             x0 = x0 * (-c) / g;
63             y0 = y0 * (-c) / g;
64 
65             LL aa = a / g;
66             LL bb = b / g;
67             LL low, high;
68             if ( aa > 0 && bb > 0 )
69             {
70                 low  = max( (x0 - x1) / bb, (y0 - y2) / aa );
71                 high = min( (x2 - x0) / bb, (y0 - y1) / aa );
72                 printf("%I64d
", high - low + 1 );
73             }
74             else if ( aa > 0 && bb < 0 )
75             {
76                 low  = max( (x2 - x0) / bb, (y0 - y2) / aa );
77                 high = min( (x0 - x1) / bb, (y0 - y1) / aa );
78                 printf("%I64d
", high - low + 1 );
79             }
80             else if ( aa < 0 && bb > 0 )
81             {
82                 low  = max( (x0 - x1) / bb, (y0 - y1) / aa );
83                 high = min( (x2 - x0) / bb, (y0 - y2) / aa );
84                 printf("%I64d
", high - low + 1 );
85             }
86             else if ( aa < 0 && bb < 0 )
87             {
88                 low  = max( (x2 - x0) / bb, (y0 - y1) / aa );
89                 high = min( (x0 - x1) / bb, (y0 - y2) / aa );
90                 printf("%I64d
", high - low + 1 );
91             }
92         }
93         else puts("0");
94     }
95     return 0;
96 }