uva 10413 - Crazy Savages(拓展欧几里得)

本文主要是介绍uva 10413 - Crazy Savages(拓展欧几里得)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：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 <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>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;
}