HDU 6004 Periodical Cicadas 中国剩余定理 + 二维RMQ

http://acm.hdu.edu.cn/showproblem.php?pid=6004


Periodical Cicadas

Time Limit: 14000/7000 MS (Java/Others)    Memory Limit: 80000/80000 K (Java/Others)

Problem Description

Nearly all cicadas spend years underground as juveniles, before emerging above ground for a short adult stage of several weeks to a few months.
The seven periodical cicada species are so named because, in any one location, all of the members of the population are developmentally synchronized they emerge as adults all at once every seven years.
The lifecycles of most periodical cicada species range from two to seventeen years, although some could be longer.
There is a forest which can be roughly divided into a matrix of size N ×M. The upper-left region is (1, 1) and the lower-right region is (N, M).
A population of periodical cicadas live within each region of the matrix. The population in region (i, j) emerged in year $a_{i,j}$ for the first time, and re-emerges every $b_{i,j}$ years. i.e. they are $b_{i,j}$ - periodical cicadas.
Given a selected rectangular area, entomologists wonder if there is a time when all cicadas in that area emerge together.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test cases begin with two integers N and M.
The following N lines each consists of M integers $a_{i,j}$ representing the year cicadas emerged in region (i, j) for the first time.
The following N more lines each consists of M integers $b_{i,j}$ representing the periodical cycle of the cicadas in that region.
Then comes a line with an integer Q representing the number of queries. The following Q lines each consists of 4 integers: $x_1, y_1, x_2, y_2,$ representing the upper-left and lower-right coordinate of the selected rectangular area.

 Output

For each test case, first output one line containing “Case #x:”, where x is the test case number (starting from 1).
The following Q lines each consists of an integer which is the year when all cicadas in the selected area emerge together for the first time or -1 if it’s impossible.

limits

$\bullet 1 ≤ T ≤ 10.$
$\bullet 1 ≤ N, M ≤ 200.$
$\bullet 0 ≤ a_{i,j} < b_{i,j} ≤ 40.$
$\bullet 1 ≤ x_1 ≤ x_2 ≤ N.$
$\bullet 1 ≤ y_1 ≤ y_2 ≤ M.$
$\bullet$ 1 ≤ Q ≤ 500000.

Sample Input

2
3 4
3 1 1 2
1 1 2 1
1 0 5 5
5 4 2 3
2 2 3 2
4 2 6 6
5
2 2 2 2
1 1 3 4
1 4 2 4
1 1 1 2
2 2 3 4
1 2
0 1
2 2
1
1 1 1 2

 Sample Output

Case #1:
1
-1
5
13
-1
Case #2:
-1

 Source

 

题意

在一个n*m的矩阵中,每个格子有一只蝉。每只蝉分别会在$ a_{i,j}$ 时间叫一声,然后每$ b_{i,j}$时间叫一声($0 ≤ a_{i,j} < b_{i,j} ≤ 40.$)。有Q次询问,每次询问从$x_1,y_1$到$x_2,y_2$区域内,所有蝉同时叫的最早的时间,如果不会同时叫,输出-1。

思路

可以把每个蝉看作同余方程,即$t_{i,j} \equiv  a_{i,j}(\mod b_{i,j} )$,每只蝉会在$t_{i,j}$时间叫,询问一个区域的时候,将区域内的所有同余方程用中国剩余定理合并即可。由于重复合并相同的方程不会对结果造成影响,可以使用二维RMQ来预处理区域内的同余方程。要注意在合并方程的时候,会出现乘法超出long long数据范围的问题。