题目链接：4596 Yet another end of the world
题目大意：给定若干组x，y，z，问是否能找到一个整数d，使得至少两组x，y，z满足y≤d%x≤z。
解题思路：首先枚举出两组x，y，z。
然后判断这两组是否能找到一个d，使得满足题目条件。
现在假设a、b，有a*x1+y1≤d≤a*x1+z1和b*x2+y2≤d≤b*x2+z2；
若两段区间有交集，必有a*x1+y1≤b*x2+z2且b*x2+y2≤a*x1+z1；
化简得a*x1-b*x2≤z2-y1 且a*x1-b*x2≥y2-z1;
若a，b有整数解，根据拓展欧几里得定理ax1+bx2=u有整数解的情况为u/gcd(x1,x2)==0;
所以若存在y2-z1≤u≤z2-y1，使得u/gcd(x1,x2)==0即可。
#include#include const int N = 1005; int n, x[N], y[N], z[N]; int gcd (int a, int b) { return b == 0 a : gcd(b, a%b); } bool judge (int t, int a, int b) { if (a % t == 0 || b % t == 0) return true; if (a < 0 && b > 0) return true; if (b/t - a/t >= 1) return true; return false; } bool solve () { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int t = gcd(x[i], x[j]); if (judge(t, y[j]-z[i], z[j]-y[i])) return false; } } return true; } int main () { while (scanf("%d", &n) == 1) { for (int i = 0; i < n; i++) scanf("%d%d%d", &x[i], &y[i], &z[i]); printf("%s\n", solve () "Can Take off" : "Cannot Take off"); } return 0; }