== include(page="template/taskheader" task_id="xcmmdc") ==
Poveste şi cerinţă...
Se dă o matrice cu $m$ linii şi $n$ coloane, cu elementele numere naturale nenule şi un număr natural nenul fixat $k$.
h2. Cerinţă
Pentru matricea dată şi numărul $k$ dat să se răspundă la $q$ întrebări de forma: “Câte submatrici pătratice de latură $L$ cu cel mai mare divizor comun al elementelor egal cu $k$ există în matricea dată?”
h2. Date de intrare
Fişierul de intrare $xcmmdc.in$ ...
Fişierului de intrare $xcmmdc.in$ conţine pe prima linie patru numere naturale nenule separate prin câte un spaţiu: $m$ şi $n$ - numărul de linii şi numărul de coloane ale matricei, $k$ – numărul natural dat şi $q$ – numărul de întrebări. Pe următoarele $m$ linii se găsesc liniile matricei. Fiecare dintre aceste linii conţine câte $n$ numere naturale separate prin câte un spaţiu – elementele liniei corespunzătoare din matrice. Următoarele $q$ linii descriu întrebările. Fiecare dintre aceste linii conţine câte un număr natural $L$ – latura submatricei din întrebarea corespunzătoare.
h2. Date de ieşire
În fişierul de ieşire $xcmmdc.out$ ...
Fişierul de ieşire $xcmmdc.out$ va conţine $q$ linii. Pe fiecare dintre aceste linii se va scrie un singur număr natural reprezentând răspunsul la întrebarea corespunzătoare din fişierul de intrare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n, m ≤ 1002$
* Pentru $50%$ din teste $1 ≤ n, m ≤ 502$
* $1 ≤ q ≤ 50002$
* $1 ≤ k ≤ 10^9^ + 2$
* Elementele matricei sunt numere naturale nenule mai mici sau egale decât $10^9^ + 2$.
* $1 ≤ L ≤ min(m, n)$ pentru fiecare întrebare
* Prin submatrice pătratică de latură $L$ se înţelege o matrice obţinută prin intersecţia a $L$ linii consecutive cu $L$ coloane consecutive din matrice.
h2. Exemplu
table(example). |_. xcmmdc.in |_. xcmmdc.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 3 3 4
3 6 2
9 12 3
2 6 3
2
1
3
2
| 2
3
0
2
|
h3. Explicaţie
...
Pentru prima şi ultima întrebare avem două submatrice:
$3 6$
$9 12$
-----
$12 3$
$6 3$
Prima submatrice se obţine prin intersecţia primelor două linii cu primele două coloane, iar a doua prin intersecţia ultimelor două linii cu ultimele două coloane.
== include(page="template/taskfooter" task_id="xcmmdc") ==
