题目链接：uva 10413 - Crazy Savages

题目大意：一座山有m个山洞，形成一个圈，现在有n个部落的人，每个部落一开始住在ci山洞，第2天会向后面移动pi个位置，一共会在这座山住li天。现在如果两个部落在同一个山洞相遇，则会发生战争，问说m最小时多少的时候，保证不会发生争斗。

解题思路:因为每个部落都有自己的存在时间，所以枚举m，然后枚举两个部落，判断他们有没有可能相遇。

假设在第k天：
ci+k?pi=a?m???(1)
cj+k?pj=b?m???(2)
由(2)-(1)得
(ci?cj+k?(pi?pj)=(a?b)?m
令A=pj?pi, B=m, C=ci?cj
然后就有A?k+B?(a?b)=C
用拓展欧几里得求出k的通解，看有没有满足0≤k≤min(li,lj)的解，有的话表示会相遇。

 #include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int maxn = 20; const int maxans = 1e6; const int INF = 0x3f3f3f3f; struct Sava { int c, p, l; }s[maxn]; int n; void gcd (int a, int b, int& d, int& x, int& y) { if (b == 0) { d = a; x = 1; y = 0; } else { gcd(b, a%b, d, y, x); y -= (a/b) * x; } } bool judge (int m) { for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { int A = s[j].p - s[i].p; int C = s[i].c - s[j].c; int L = min(s[i].l, s[j].l); int d, x, y; gcd(A, m, d, x, y); if (C % d) continue; int up = INF, lower = -INF; if (m / d > 0) { up = min(up, (int)floor( (L * d * 1.0 - x * C * 1.0) / m)); lower = max(lower, (int)ceil( (-x * C * 1.0) / m)); } else { up = min(up, (int)floor( (-x * C * 1.0) / m)); lower = max(lower, (int)ceil( (L * d * 1.0 - x * C * 1.0) / m)); } if (up >= lower) return false; } } return true; } int main () { int cas; scanf("%d", &cas); while (cas--) { int star = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d%d", &s[i].c, &s[i].p, &s[i].l); star = max (star, s[i].c); } for (int i = star; i <= maxans; i++) { if (judge(i)) { printf("%d\n", i); break; } } } return 0; }