题目描述
克里特岛以野人群居而著称。岛上有排列成环形的 m 个山洞。这些山洞顺时针编号为 1,2,…,m。岛上住着 n 个野人，一开始依次住在山洞 C1,C2,…,Cn 中，以后每年，第 i 个野人会沿顺时针向前走 Pi 个洞住下来。
每个野人 i 有一个寿命值 Li，即生存的年数。
下面四幅图描述了一个有 6 个山洞，住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为 1,2,3；每年要走过的洞穴数依次为 3,7,2；寿命值依次为 4,3,1。
奇怪的是，虽然野人有很多，但没有任何两个野人在有生之年处在同一个山洞中，使得小岛一直保持和平与宁静，这让科学家们很是惊奇。他们想知道，至少有多少个山洞，才能维持岛上的和平呢？
输入格式
第 1 行为一个整数 n(1≤n≤15)，即野人的数目。
第 2 行到第 N+1 每行为三个整数 Ci,Pi,Li(1≤Ci,Pi≤100,0≤Li≤106)，表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。
输出格式
仅包含一个数 M，即最少可能的山洞数。输入数据保证有解，且 M 不大于 106。
输入输出样例
输入 #1复制
3 1 3 4 2 7 3 3 2 1
输出 #1复制
6
说明/提示
1≤N≤15，1≤Ci,Pi≤100，0≤Li≤106
保证 M≤106
代码实现：
#include <cstdio> #include <iostream> using namespace std; const int maxn = 20, maxm = 1e6; int len[maxn], pos[maxn], val[maxn]; int n, m; int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int res = exgcd(b, a % b, x, y), t = x; x = y; y = t - a / b * y; return res; } bool check(int i, int j, int b) { int a = pos[j] - pos[i], d = val[i] - val[j], x, y; if (a < 0) a = -a, d = -d; int g = exgcd(a, b, x, y); if (d % g) return 1; return ((x * (d / g) % (b / g) + (b / g)) % (b / g)) > min(len[i], len[j]); } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d%d%d", val + i, pos + i, len + i); m = max(m, val[i]); } for (int i = m; i <= maxm; ++i) { bool ok = 1; for (int j = 1; j <= n && ok; ++j) for (int k = 1; k <= n && ok; ++k) if (k != j && !check(j, k, i)) ok = 0; if (ok) { printf("%d\n", i); break; } } return 0; }
