题目描述：
输入格式：第一行一个整数，表示野人的数目。
第2~n+行每行三个整数ci, pi, li，表示每个野人初始住的洞穴编号，每年走过的洞穴数和寿命值。
输出格式：一个数m表示最少的洞穴数。
输入样例：
3 1 3 4 2 7 3 3 2 1
输出样例：
6
//该样例对应题目中描述的例子
解析：对于每个m，对于每两个野人可以列出式子 c[i] + p[i] * x = c[j] + p[j] * x (mod m)
转化为方程即为 (p[i] - p[j]) * x + m * k = c[j] - c[i]
于是用扩欧求解 x 即可，若无解或解出的 x 比两个野人寿命的最小值大，说明两个野人在有生之年不会相会。
这样判断完每一对野人，若每一对都成立，则说明这个m可行。
由于数据很小，所以m暴力枚举即可。
代码如下：
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 const int maxn = 20; 6 int n, c[maxn], p[maxn], l[maxn], mx, x, y; 7 8 int read(void) { 9 char c; while (c = getchar(), c < '0' || c >'9'); int x = c - '0'; 10 while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; 11 } 12 13 int exgcd(int a, int b) { //扩欧 14 if (!b) { 15 x = 1; y = 0; return a; 16 } 17 int d = exgcd(b, a % b); 18 int t = x; x = y; y = t - (a / b) * y; 19 return d; 20 } 21 22 int pd(int m) { 23 for (int i = 1; i <= n; ++ i) 24 for (int j = i + 1; j <= n; ++ j) { 25 int a = p[i] - p[j], b = m, d = c[j] - c[i]; 26 if (a < 0) a = -a, d = -d; //由于a为非负数，所以若a<0，则将a变为-a 27 int g = exgcd(a, b); 28 if (d % g) continue; 29 a /= g; b /= g; d /= g; x *= d; 30 x = (x % b + b) % b; //求最小的正整数解 31 if (!x) x += b; 32 if (x <= min(l[i], l[j])) return 0; //不成立，直接退出 33 } 34 return 1; 35 } 36 37 int main() { 38 n = read(); 39 for (int i = 1; i <= n; ++ i) c[i] = read(), p[i] = read(), l[i] = read(), mx = max(mx, c[i]); 40 for (int i = mx; i ; ++ i) { //枚举m 41 if (pd(i)) return printf("%d", i); 42 } 43 return 0; 44 }
转载于:https://www.cnblogs.com/Gaxc/p/9913005.html
相关资源：JAVA上百实例源码以及开源项目