By

文章目录
  1. 1. 题意
  2. 2. 分析

原题

题意

有n个虫洞，每个虫洞有三个参数X、Y、Z，如果存在一个ID，可以使ID%X在[Y,Z]区间内，则这个虫洞将可以吸引飞船，但是，如果同时两个或者两个以上的虫洞可以吸引飞船，那么飞船将被撕碎，不能通过。

分析

由于我们的目的是：确定每两个虫洞的参数之间不存在一个ID，ID满足：
Ax1+C=ID
BX2+D=ID
X1，X2是两个虫洞的X参数，C在Y1,Z1之间取值，D在Y2，Z2之间取值。
然后，我当时就。。卡住了，把这个式子转化成了两个同余方程，但是其实不用计算ID，因为我们的目的是存在ID，然后C,D都是存在的，所以只要A,B存在就可以了，所以联立式子变成一个二元一次不定方程，然后根据数论的不定方程的相关知识：
AX1-Bx2=D-C
X1≡(D-C)(mod X2)
这个同余方程有解的条件是(D-C)%gcd(x1,x2)==0
然后对每两组虫洞的参数，看在D-C取值范围内的是否存在gcd(x1,x2)的整数倍，队友是用容斥判断的，我写的是分类讨论，虽然被基友说过很多次了。。不要老用分类讨论，要证明要证明，分类讨论通常会漏掉很多情况（比如上次的西电校赛网络赛的贪心。。），嘛这次以后！！！我会改的！！！（不过很多情况下第一反应还是分类讨论啊。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define N 1007
using namespace std;
long long x[N],y[N],z[N],n;
long long gcd(long long a,long long b){
    return (b==0)?a:gcd(b,a%b);
}
bool solve(int i,int j){
    int mn,mx,mmn,mmx,g;
    g=gcd(x[i],x[j]);
    mn=y[i]-z[j];//可以取的gcd的范围
    mx=z[i]-y[j];
    //cout<<g<<endl;
    if(g>=min(fabs(mx),fabs(mn))&&g<=max(fabs(mx),fabs(mn))){
        return true;
    }
    else if(g<min(fabs(mx),fabs(mn))){
        mmn=mn/g;
        mmx=mx/g;//cout<<mmx<<' '<<mmn;
        return mmn!=mmx;
    }
    else if(g>max(fabs(mx),fabs(mn))){
        if(0>=min(mx,mn)&&0<=max(mx,mn)){
            return true;
        }
        return false;
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        int p=0;
        for(int i=0;i<n;i++){
            scanf("%I64d%I64d%I64d",&x[i],&y[i],&z[i]);
            for(int j=0;j<i;j++){//cout<<solve(i,j);
                if(solve(i,j)){
                    p=1;
                }
            }
        }
        if(p==1){
            printf("Cannot Take off\n");
        }
        else{
            printf("Can Take off\n");
        }

    }
    return 0;
}
文章目录
  1. 1. 题意
  2. 2. 分析