题目链接:Click here~~
题意:
有 n 个三元组 {x,y,z},问是否存在一个任意数 num 和一对 i,j,使 num % x[i] 和 num% x[j] 的值分别落在对应的区间 [ y[i] , z[i] ] 和[ y[j] , z[j] ] 中。
解题思路:
由于 n 是 1e3,所以可以直接枚举 i,j,关键是如何判断他们是否存在满足这样要求的值。
不妨设 num % x[i] = a , num % x[j] = b,则 num = k1 * x[i] + a , num = k2 * x[j] + b 。
将 num 消掉,可以得出 k1 * x[i] + a = k2 * x[j] + b 从而 x[i] * k1 - x[j] * k2 = b - a。
发现这是一个不定方程,方程有解当且仅当 (b-a) % gcd(x[i],x[j]) = 0。
由于 a , b 的值都必须属于对应的 [y,z] 区间,所以可以得到 b-a 的范围。
得出范围后,只需要判断这个范围中是否存在 % gcd(x[i],x[j]) = 0 的值即可。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std; const int N = 1005; int x[N],a[N],b[N]; inline int gcd(int a,int b) { return b ? gcd(b,a%b) : a; } bool meet(int i,int j) { int l = a[j] - b[i]; int r = b[j] - a[i]; int d = gcd(x[i],x[j]); if(l%d==0 || r%d==0) return true; else return l/d != r/d; } int main() { int n; while(~scanf("%d",&n)) { for(int i=0;i<n;i++) scanf("%d%d%d",&x[i],&a[i],&b[i]); bool ok = true; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(meet(i,j)) { ok = false; goto end; } end: puts(ok?"Can Take off":"Cannot Take off"); } return 0; }