Fişierul intrare/ieşire:xcmmdc.in, xcmmdc.outSursăONI 2014 Clasele 11-12
AutorRadu Stefan VoroneanuAdăugată deMihai22eMihai Ionut Enache Mihai22e
Timp execuţie pe test1.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.inxcmmdc.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content