hdu 4596 Yet another end of the world

本文从WordPress迁移而来, 查看全部WordPress迁移文章

数学转化

题意:问是否存在一个数字,模X1的值落在[Y1,Z1]中,并且模X2的值落在[Y2,Z2]中

假设存在num

1
2
3
4
5
6
num % x1 = a
num % x2 = b
num = k1 * x1 + a
num = k2 * x2 + b
k1 * x1 + a = k2 * x2 + b
x1 * k1 + x2 * k2 = b - a

x1和x2是已知的,k1,k2未知,相当于解线性返程

设 d = gcd(x1,x2)

那么 x1 k1 + x2 k2 = d 一定存在整数解

如果 (b-a)是d的倍数那么 x1 k1 + x2 k2 = b - a 也有解

而b - a是有范围的

1
2
3
4
5
y2 <= b <= z2
y1 <= a <= z1
y2 - z1 <= b-a <= z2 - y1
L = y2 - z1
R = z2 - y1

只要[L,R]里面有d的倍数即可

if(L % d == 0 || R % d == 0) true 这显然可以

否则的话

1
2
3
s1 = L / d
s2 = R / d
s2 - s1 >= 1 也是可以的

这也是显然的,不需要过多证明

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1010
#define LL long long

int n,x[N],y[N],z[N];
bool res;

LL gcd(LL a , LL b){
return b == 0 ? a : gcd(b,a%b);
}

bool check(int i,int j){
LL d = gcd(x[i],x[j]);
LL L = y[j] - z[i];
LL R = z[j] - y[i];
if(L % d == 0 || R % d == 0) return true;
LL s1 = L / d;
LL s2 = R / d;
if(s2 - s1 >= 1) return true;
return false;
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 0; i < n; i++)
scanf("%I64d%I64d%I64d",&x[i],&y[i],&z[i]);
res = false;
for(int i = 0; i < n; i++){

for(int j = i+1; j < n; j++){
res = check(i,j);
if(res) break;
}
if(res) break;
}
if(res) puts("Cannot Take off");
else puts("Can Take off");
}
return 0;
}