hdu-4596(扩展欧几里得解一次不定方程)

电玩女神 2022-06-10 09:57 94阅读 0赞

Problem Description

In the year 3013, it has been 1000 years since the previous predicted rapture. However, the Maya will not play a joke any more and the Rapture finally comes in. Fortunately people have already found out habitable planets, and made enough airships to convey all the human beings in the world. A large amount of airships are flying away the earth. People all bear to watch as this planet on which they have lived for millions of years. Nonetheless, scientists are worrying about anther problem…  
As we know that long distance space travels are realized through the wormholes, which are given birth by the distortion of the energy fields in space. Airships will be driven into the wormholes to reach the other side of the universe by the suction devices placed in advance. Each wormhole has its configured attract parameters, X, Y or Z. When the value of ID%X is in \[Y,Z\], this spaceship will be sucked into the wormhole by the huge attraction. However, the spaceship would be tear into piece if its ID meets the attract parameters of two wormholes or more at the same time.  
All the parameters are carefully adjusted initially, but some conservative, who treat the Rapture as a grain of truth and who are reluctant to abandon the treasure, combine with some evil scientists and disrupt the parameters. As a consequence, before the spaceships fly into gravity range, we should know whether the great tragedy would happen or not. Now the mission is on you.

Input

Multiple test cases, ends with EOF.  
In each case, the first line contains an integer N(N<=1000), which means the number of the wormholes.  
Then comes N lines, each line contains three integers X,Y,Z(0<=Y<=Z<X<2\*10 9).

Output

If there exists danger, output “Cannot Take off”, else output “Can Take off”.

Sample Input

2 7 2 3 7 5 6 2 7 2 2 9 2 2

Sample Output

Can Take off Cannot Take off

题目题意：题目大意是给你，n个x,y,z,如果存在一个整数d，满足d%x1属于\[y1,z1\],  d%x2属于\[y2,z2\],那么就输出"Cannot Take off",如果没有任何数满足就输出"Can Take off  
".

题目分析:因为n的范围不大，所以我们可以暴力枚举每种组合，关键就是这么去判断，是否满足条件？

依题意我们可以知道，第一组x1,y1,z1,能够表示的数为k1\*x1+y1<=d<=k1\*x1+z1,同理我们可以表示第二组k2\*x2+y2<=d<=k2\*x2+z2,那么题目的条件就是这俩个区间有交集，

简单画图可知，这俩个范围有交集，那么就得满足k1\*x1+y1<=k2\*x2+z2&&k1\*x1+z1>=k2\*x2+y2;

化简得:

k1\*x1-k2\*x2<=z2-y1

k1\*x1-k2\*x2>=y2-z1

也就是说只要有一个数i在\[y2-z1,z2-y1\]范围内，且使得不定方程有解，那么就可以判断了。

对于方程ax+by=c有解的充要条件是c%gcd(a,b)==0,思路清楚了，就可以写代码了。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    
    const int maxn=1e3+10;
    int n;
    struct note
    {
        int x,y,z;
    }p[maxn];
    
    int gcd(int a,int b)
    {
        if (b==0) return a;
        else gcd(b,a%b);
    }
    bool check(int a,int b,int l,int r)
    {
        if (r<l) return false;//如果范围都不存在的话，肯定就不在咯
        int d=gcd(a,b);
        for (int i=l;i<=r;i++) {//枚举范围内的每一个
            if (i%d==0)
                return true;
        }
        return false;
    }
    bool solve()
    {
        for (int i=0;i<n-1;i++) {
            for (int j=i+1;j<n;j++) {//挨个枚举所有的组合
                if (check(p[i].x,p[j].x,p[j].y-p[i].z,p[j].z-p[i].y)) return false;
            }
        }
        return true;
    }
    int main()
    {
        while (scanf("%d",&n)!=EOF) {
            for (int i=0;i<n;i++)
                scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
            if (solve())
                printf("Can Take off\n");
            else
                printf("Cannot Take off\n");
        }
        return 0;
    }