题目链接: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。
发现这是一个不定方程,方程有解当且仅......
阅读全文