xcmmdc

Time limit: 1.25s
Memory limit: 128MB
Input: xcmmdc.in
Output: xcmmdc.out

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 şi precizări

  • 1 ≤ n, m ≤ 1002
  • Pentru 50% din teste 1 ≤ n, m ≤ 502
  • 1 ≤ q ≤ 50 002
  • 1k109+21 ≤ k ≤ 10^9+2
  • Elementele matricei sunt numere naturale nenule mai mici sau egale decât 109+210^9+2.
  • 1 ≤ L ≤ min(m,n) pentru fiecare întrebare

Exemplu

xcmmdc.in

3 3 3 4
3 6 2
9 12 3
2 6 3
2
1
3
2

xcmmdc.out

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.

Problem info

ID: 231

Editor: liviu

Author:

Source: ONI 2014 XI-XII: Ziua 2 Problema 3

Tags:

ONI 2014 XI-XII

Log in or sign up to be able to send submissions!