| Fişierul intrare/ieşire: | xcmmdc.in, xcmmdc.out | Sursă | ONI 2014 Clasele 11-12 |
| Autor | Radu Stefan Voroneanu | Adăugată de |  Mihai Ionut Enache •Mihai22e |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Xcmmdc
Se dă o matrice cu m linii şi n coloane, cu elementele numere naturale nenule şi un număr natural nenul fixat k.
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ă?”
Date de intrare
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.
Date de ieşire
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.
Restricţii
- 1 ≤ n, m ≤ 1002
- Pentru 50% din teste 1 ≤ n, m ≤ 502
- 1 ≤ q ≤ 50002
- 1 ≤ k ≤ 109 + 2
- Elementele matricei sunt numere naturale nenule mai mici sau egale decât 109 + 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.
Exemplu
| xcmmdc.in | xcmmdc.out |
|---|---|
| 3 3 3 4 3 6 2 9 12 3 2 6 3 2 1 3 2 | 2 3 0 2 |
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.
