h2. 'Euclid':problema/euclid

Problema se poate rezolva calculand gcd-ul patratelor ce au lungimile laturilor puteri ale lui $2$. Astfel tinem o matrice $V[0..LOGM][0..LOGN][1..M][1..N]$, unde $V[di][dj][i][j]$ reprezinta gcd-ul numerelor din dreptunghiul cu colturile in $(i, j), (i + 2^di^ - 1, j + 2^dj^ - 1)$. Aceasta matrice se poate calcula cu usurinta in $O(logM * logN * M * N)$ incepand cu puterile mai mici ale lui $2$, in stil bottom-up. Putem apoi vedea in $O(1)$ care este gcd-ul elementelor din dreptunghiul cu colturile in $(i, j), (i + w - 1, j + h - 1)$. Pentru aceasta, mai intai sa luam $di = [log h]$ si $dj = [log w]$. Numarul cautat este $gcd(V[di][dj][i][j], V[di][dj][i][j + w - dj], V[di][dj][i + h - di][dj], V[di][dj][i + h - di][j + w - dj])$. Nu mai ramane decat sa luam maximul dintre toate dreptunghiurile posibile. Aceasta solutie foloseste $O(logN * logM * N * M)$ spatiu si timp.

Problema se poate rezolva calculand gcd-ul patratelor ce au lungimile laturilor puteri ale lui $2$. Astfel tinem o matrice $V[0..LOGM][0..LOGN][1..M][1..N]$, unde $V[di][dj][i][j]$ reprezinta gcd-ul numerelor din dreptunghiul cu colturile in $(i, j), (i + 2^di^ - 1, j + 2^dj^ - 1)$. Aceasta matrice se poate calcula cu usurinta in $O(logM * logN * M * N)$ incepand cu puterile mai mici ale lui $2$, in stil bottom-up. Putem apoi vedea in $O(1)$ care este gcd-ul elementelor din dreptunghiul cu colturile in $(i, j), (i + w - 1, j + h - 1)$. Pentru aceasta, mai intai sa luam $di = [log h]$ si $dj = [log w]$. Numarul cautat este $gcd(V[di][dj][i][j], V[di][dj][i][j + w - 2^dj^], V[di][dj][i + h - 2^di^][dj], V[di][dj][i + h - 2^di^][j + w - 2^dj^ ])$. Nu mai ramane decat sa luam maximul dintre toate dreptunghiurile posibile. Aceasta solutie foloseste $O(logN * logM * N * M)$ spatiu si timp.

Desi solutia de mai sus ar fi obtinut punctaj maxim, problema se poate rezolva si mai elegant. Astfel, in loc sa tinem tabela cu toate puterile lui $2$ putem calcula $A[1..M][1..N]$ unde $A[i][j]$ e gcd-ul elementelor din dreptunghiul cu colturile in $(i, j), (i, j + w - 1)$. Aceasta matrice poate fi calculata in $O(logN * N * M)$ folosind acelasi rationament ca mai sus. De asemenea, trebuie sa mai calculam o matrice $B[1..M][1..N]$ unde $B[i][j]$ tine gcd-ul elementelor din $A$ din dreptunghiul $(i, j), (i + h - 1, j)$. Aceasta matrice se calculeaza analog cu matricea A. Rezultatul este $max(B[i][j])$, pentru toate perechile $i, j$ a.i $i + h - 1 ≤ M$ si $j + w - 1 ≤ N$. Acest algoritm ruleaza in $O((logN + logM) * N * M)$ timp si $O(N * M)$ memorie.