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;

    }
}
==