2013 南京邀请赛 K题 yet another end of the world

 1 /**
 2 大意：给定一组x[],y[],z[]   确定有没有两个不同的x[i], x[j] 看是否存在一个ID使得
 3      y[i]<=ID%x[i]<=z[i]
 4      y[j]<=ID%x[j]<=z[j]
 5 设ID%x[i] = a   ID%x[j] = b 
 6 ===〉ID+x[i]*x=a,   ID+x[j]*y = b;
 7 两式相减得   x[j]*y - x[i]*x = b-a;
 8 若是有解 就是(b-a)%gcd(x[i],x[j]) == 0
 9 就是看b-a的范围内是否有数是 gcd(x[i],x[j])  的倍数
10 因为       y[j]<=b<=z[j]          y[i]<=a<=z[i]
11 所以       y[j]-z[i]<=b-a<=z[j]-y[i]
12 
13 欠缺； 还是思路不够，，做题太少。。
14 **/
15 
16 #include <iostream>
17 #include <algorithm>
18 using namespace std;
19 long long x[1010],y[1010],z[1010];
20 
21 long long gcd(long long a,long long b){
22     if(b==0)
23         return a;
24     return gcd(b,a%b);
25 }
26 
27 bool check2(int d,int l,int r){
28     if(l%d==0||r%d==0)
29         return true;
30     if((r-l+1)>=d)
31         return true;
32     int t1 = l/d;
33     int t2 = r/d;
34     if(t1!=t2)
35         return true;
36     else
37         return false;
38 }
39 
40 bool check(int i,int j){
41     if(y[i]>z[j]||y[j]>z[i]){
42         if(z[j]<y[i])
43             swap(i,j);
44         long long d = gcd(x[i],x[j]);
45         if(check2(d,y[j]-z[i],z[j]-y[i]))
46             return true;
47         else
48             return false;
49     }else
50         return true;
51 }
52 
53 int main()
54 {
55     int n;
56     while(cin>>n){
57         for(int i=0;i<n;i++)
58             cin>>x[i]>>y[i]>>z[i];
59         bool flag = false;
60         for(int i=0;i<n;i++){
61             for(int j=i+1;j<n;j++){
62                 if(check(i,j)){
63                     flag = true;
64                     break;
65                 }
66             }
67         }
68         if(!flag){
69             cout<<"Can Take off"<<endl;
70         }else{
71             cout<<"Cannot Take off"<<endl;
72         }
73     }
74     return 0;
75 }