一坨差分约束题

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

别看了，上面都是水题！！！

 

下面才是一些有脑题：

 

 

题意：

给定一个最大400*400的矩阵，每次操作可以将某一行或某一列乘上一个数，问能否通过这样的操作使得矩阵内的每个数都在[L,R]的区间内

就是是否存在$a_i$,$b_j$，使得$ L leq c_{i,j} imes frac{a_i}{b_j} leq R (1 leq i leq n,1 leq j leq m)$成立。

好嘛，我们来推推式子：

$ frac{L}{c_{i,j}} leq frac{a_i}{b_j} leq frac{R}{c_{i,j}} $

$ log(frac{L}{c_{i,j}}) leq log(frac{a_i}{b_j}) leq log(frac{R}{c_{i,j}}) $

$ log(frac{L}{c_{i,j}}) leq log(a_i) - log(b_j) leq log(frac{R}{c_{i,j}}) $

然后就懂怎么差分了吧，呵呵。