#189Programare

Elemente egale cu c.m.m.d.c. dintre suma liniei și produsul coloanei

Enunț

Se citește o matrice n × m cu elemente numere naturale. Afișați elementele care au proprietatea că sunt egale cu cel mai mare divizor comun al sumei elementelor de pe linia lor și al produsului elementelor de pe coloana lor.

Pentru datele de intrare:

se afișează:

3 5 3

Rezolvare

C++

#include <iostream>
using namespace std;

int a[105][105];
long long sl[105], pc[105];                 // suma pe linie, produs pe coloana

long long cmmdc(long long x, long long y) {
    while (y) { long long r = x % y; x = y; y = r; }
    return x;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];

    for (int i = 0; i < n; i++) { sl[i] = 0; for (int j = 0; j < m; j++) sl[i] += a[i][j]; }
    for (int j = 0; j < m; j++) { pc[j] = 1; for (int i = 0; i < n; i++) pc[j] *= a[i][j]; }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (a[i][j] == cmmdc(sl[i], pc[j]))
                cout << a[i][j] << " ";
    cout << "\n";
    return 0;
}

Cum funcționează

Problema combină trei lucruri deja cunoscute, iar dificultatea vine din organizare, nu din algoritm.

Pasul 1 — precalculează. Suma unei linii și produsul unei coloane nu depind de elementul curent, ci doar de indicele lui. Dacă le recalculezi în interiorul buclei de verificare, faci aceeași muncă de zeci de ori. Se calculează o dată, în doi vectori:

sl[i] = suma elementelor de pe linia i
pc[j] = produsul elementelor de pe coloana j

Atenție la inițializare: suma pornește de la 0, produsul de la 1. Un produs pornit de la 0 rămâne 0 la infinit.

Pasul 2 — c.m.m.d.c. cu algoritmul lui Euclid, aici în formă iterativă. Ideea e că cel mai mare divizor comun al lui x și y e același cu cel al lui y și restul lui x la y; se repetă până restul devine 0.

Pasul 3 — verificarea, care acum e o singură linie.

Verificare pe exemplul din enunț: sumele pe linii sunt 9, 25, 21; produsele pe coloane sunt 12, 256, 45, 24. Elementul a[0][3] = 3 are cmmdc(9, 24) = 3 — se afișează. Elementul a[1][2] = 5 are cmmdc(25, 45) = 5 — se afișează. Elementul a[2][0] = 3 are cmmdc(21, 12) = 3 — se afișează. Rezultatul e 3 5 3, exact ca în model.

Capcana reală e produsul. Enunțul nu limitează valorile elementelor. O coloană cu 100 de elemente egale cu 10 dă un produs de 10^100 — imposibil de reprezentat. long long amână problema, nu o rezolvă. La examen, menționează limitarea: e exact genul de observație care diferențiază o lucrare bună de una corectă.

Greșeli frecvente

Produsul inițializat cu 0 — toate produsele ies 0, iar cmmdc(s, 0) = s, deci se afișează elementele egale cu suma liniei lor. Rezultat plauzibil și complet greșit.
Recalcularea sumei și a produsului în bucla interioară — corect, dar de n·m ori mai lent; la limitele din enunț încă trece, la altele nu.
int pentru produs — depășire tăcută, cu rezultat negativ.
Confundarea liniei cu coloana — „suma elementelor de pe linia lor" înseamnă sl[i], iar „produsul elementelor de pe coloana lor" înseamnă pc[j]. Inversarea trece de compilare și dă alt răspuns.

Apariții

Galati 2026 — problema 29 · sursa oficială