h3. Rezolvare

Pentru un dreptunghi cu laturile paralele cu axele de coordonate de lungime $M$ şi lăţime $N$ avem că numărul de puncte situate strict în interiorul dreptunghiului este $(M - 1)*(N - 1)$, iar numărul de puncte situate pe laturile poligonului este $2M + 2N$. Dacă notăm cu $B$ numărul de puncte de pe laturi, cu $I$ numărul de puncte situate strict în interiorul unui dreptunghi şi cu $A$ aria dreptunghiului, observăm că $I + B/2 - 1 = (M - 1) * (N - 1) + M + N - 1 = M * N = A$.

Pentru un dreptunghi cu laturile paralele cu axele de coordonate de lungime $M$ şi lăţime $N$ avem că numărul de puncte situate strict în interiorul dreptunghiului este $(M - 1) * (N - 1)$, iar numărul de puncte situate pe laturile poligonului este $2M + 2N$. Dacă notăm cu $B$ numărul de puncte de pe laturi, cu $I$ numărul de puncte situate strict în interiorul unui dreptunghi şi cu $A$ aria dreptunghiului, observăm că $I + B/2 - 1 = (M - 1) * (N - 1) + M + N - 1 = M * N = A$.

În cazul triunghiurilor dreptunghice ce au două catete vom vedea că această formulă se păstrează. Evident avem că $A = (M * N)/2$. Pe ipotenuza triunghiului vom avea $D$ puncte ({$D = cmmdc(M, N) + 1$}, dar aceasta nu ne interesează pe moment). Rezultă că numărul de puncte de pe laturile triunghiului este $B = M + N + D - 1$. Numărul de puncte $I$ din interiorul triunghiului este numărul de puncte din interiorul dreptunghiului $(M - 1) * (N - 1)$ din care se scad punctele interioare de pe diagonala $D - 2$, rezultatul împărţindu-se apoi la $2$. De aici avem $I = ((M - 1) * (N - 1) - D + 2) / 2$.
Verificăm formula $I + B/2 - 1 = (M - 1) * (N - 1)/2 - D/2 + 1 + M/2 + N/2 + D/2 + 1/2 = (M * N)/2$. Deci formula se verifică şi pe astfel de triunghiuri.

Astfel, am ajuns la următorul algoritm:
==code(c) |

long num = 0;
for (long h = 2; h <= N + 1; h++) {
    for (long w = 2; w <= M + 1; w++) {

long long num = 0, laux = 0 ;
for (int h = 2; h <= N + 1; h++) {
    for (int w = 2; w <= M + 1; w++) {

        laux = (h - 2) * (w - 2) + h * w - cmmdc(h - 1, w - 1) - 2;

        num += (N - h + 1) * (M - w + 1) * laux;

        num += (N - h + 2) * (M - w + 2) * laux;

    }
}
==

Acest algoritm are complexitatea $O(N*M log N)$ şi nu s-ar fi încadrat în timpul impus, deoarece marea parte a calculelor este efectuată în determinarea celui mai mare divizor comun a două numere. Având în vedere că numerele folosite sunt între $1$ şi $N$ respectiv între $1$ şi $M$, putem să precalculăm o matrice $CMMDC[X][Y]$, $1 ≤ X ≤ N$ şi $1 ≤ Y ≤ M$, în $O(N * M)$. Astfel, complexitatea soluţiei a fost redusă la $O(N * M)$. Mai putem optimiza factorii constanţi ai soluţiei observând că într-un triunghi de dimensiuni $H * W$ poate fi înscris acelaşi număr de dreptunghiuri ca şi într-un triunghi $W * H$. Acest artificiu aproape dublează viteza algoritmului. Menţionăm că aceleaşi optimizări pot fi făcute şi la problema cu triunghiuri.

Acest algoritm are complexitatea $O(N*M log N)$ şi nu s-ar fi încadrat în timpul impus, deoarece marea parte a calculelor este efectuată în determinarea celui mai mare divizor comun a două numere. Având în vedere că numerele folosite sunt între $1$ şi $N$ respectiv între $1$ şi $M$, putem să precalculăm o matrice $CMMDC[X][Y]$, $1 ≤ X ≤ N$ şi $1 ≤ Y ≤ M$, în $O(N * M)$. Astfel, complexitatea soluţiei a fost redusă la $O(N * M)$. Mai putem optimiza factorii constanţi ai soluţiei observând că într-un dreptunghi de dimensiuni $H * W$ poate fi înscris acelaşi număr de dreptunghiuri ca şi într-un dreptunghi $W * H$. Acest artificiu aproape dublează viteza algoritmului. Menţionăm că aceleaşi optimizări pot fi făcute şi la problema cu triunghiuri.

h2(#concluzii). Concluzii