Question

Cerința
Se dă o matrice cu m linii şi n coloane, având elementele numere naturale nenule. Aflaţi câte coloane ale matricei au produsul elementelor divizibil cu un număr dat p.

Date de intrare
Fișierul de intrare memory003.in conține pe prima linie numerele m, n şi p, iar pe următoarele m linii câte n numere naturale separate prin spații, reprezentând elementele matricei.

Date de ieșire
Fișierul de ieșire memory003.out va conține pe prima linie numărul de coloane ale matricei pentru care produsul elementelor este divizibil cu p.

Restricții și precizări
1 ≤ m ≤ 1.000
1 ≤ n ≤ 300
1 ≤ p ≤ 1.000.000.000
elementele matricei sunt mai mici sau egale cu 100

Exemplu
memory003.in

2 3 10
4 7 5
25 8 6
memory003.out

2
Explicație
Produsul elementelor pe coloane este 100, 56, respectiv 30. Avem astfel două coloane cu produsul elementelor divizibil cu 10.

Answer 1

#include <bits/stdc++.h>

using namespace std;

ifstream fin("memory003.in");

ofstream fout("memory003.out");

int n,m,x[305][105],y,s;  // retinem in x pt fiecare coloana frecventa  

                         //factorilor primi din descompunerea elementelor pe coloana

long p,t[105];

int main()

{

   int i,j,d,pu;

   fin >> m >> n >> p;

   for( i=1; i<=m; i++)

       for( j=1; j<=n; j++){

           fin >> y;                    // descompunem fiecare element in factori primi atunci cand il citim

           pu=0;                        //si il retinem in matrice  

           while( y % 2 == 0)  

                 pu++,y/=2;

           x[j][2] += pu;

           d = 3;

           while( d * d <= y ){

           pu = 0;

           while( y % d == 0 )

                pu++,y/=d;

           x[j][d] += pu;

           d += 2;

           }

           if( y > 1 ) x[j][y] ++;

       }

   bool ok = true;

   pu=0;

   while( p % 2 == 0)

       pu++,p/=2;               //descompunem nr dat in factori primi si retinem frecventa factorilor in t

   t[2] += pu;                    

   d = 3;

   while( d * d <= p ){

       pu = 0;

       while( p % d == 0 )

           pu++,p/=d;

       if(pu){

           if(d<=100) t[d] += pu;

           else ok = false;

       }

       d += 2;

   }

   if( p > 1 ){                //!!!E necesar ca acel nr sa nu aiba factor prim in descompunere mai mare ca 100  

       if(p <= 100) t[p]++;    // Daca se intampla acest lucru e evident ca produsul coloanei nu se divide cu acesta  

       else ok = false;        

   }

   if(!ok) fout << 0;

   else{

   for( j=1; j<=n; j++){          

       bool o = true;

       for( i=2; i<=100; i++)

           if( t[i] > x[j][i])      //Factorii primi ai numarului trebuie sa fie mai mari sau egali decat cei ai produsului

              o = false;            //coloanei respective

       if(o) s++;     //variabila s reprezinta nr de coloane care au produsul elementelor divizibil cu p

   }

   fout << s;

   }

   return 0;

}