# PBinfo #1364 – produs3 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Se dă un şir cu n numere naturale nenule care sunt divizibile doar cu numerele prime 2, 3 sau 5. Determinaţi numărul secvenţelor din şir pentru care produsul elementelor este pătrat perfect.

Date de intrare
Fișierul de intrare produs3.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule divizibile doar cu numerele prime 2, 3 sau 5, separate prin spații.

Date de ieșire
Fișierul de ieșire produs3.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir pentru care produsul elementelor este pătrat perfect.

Restricții și precizări

1 ≤ n ≤ 1.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu:
produs3.in

5
12 3 4 5 45
produs3.out

6
Explicație
În şirul dat sunt 6 secvenţe pentru care produsul elementelor este pătrat perfect:

12 , 3
12 , 3 , 4
4
5 , 45
4 , 5 , 45
12 , 3 , 4 , 5 , 45

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream f("produs3.in");
ofstream g("produs3.out");
long long n,i,j,k,i1,j1,k1,d[22],t[16],c[12],p,e2[1000002],e3[1000002],e5[1000002],exp2,exp3,exp5;
long long cod,sol,viz[10],x;
int main()
{
    f >> n ;
    // calculez puterile lui 2,3 si 5 mai mici decat 1000000
    d[0]=1;
    i=0;
    while(d[i]<1000000){i++; d[i]=d[i-1]*2;}
    i--;
    t[0]=1;
    j=0;
    while(t[j]<1000000){j++; t[j]=t[j-1]*3;}
    j--;
    c[0]=1;
    k=0;
    while(c[k]<1000000){k++; c[k]=c[k-1]*5;}
    k--;
    // calculez numerele mai mici decat 1000000 ce sunt divizibile doar cu 2, 3 sau 5
    for(i1=0;i1<=i;i1++)
      for(j1=0;j1<=j;j1++)
        for(k1=0;k1<=k;k1++)
           {
               p=d[i1]*t[j1]*c[k1];
               if(p<1000000)
                {
                    e2[p]=i1;
                    e3[p]=j1;
                    e5[p]=k1;
                }
           }
     // citesc numerele si formez exponentii cumulati ai lui 2, 3 si 5
     exp2=0;exp3=0;exp5=0;
     viz[0]=1;
     for( i=1 ; i<=n ; i++)
     {
         f >> x ;
         exp2=exp2+e2[x];
         exp3=exp3+e3[x];
         exp5=exp5+e5[x];
         cod=(exp2%2)*4+(exp3%2)*2+exp5%2;
         viz[cod]++;
     }
     // Numar perechile de coduri de acelasi tip care se pot forma, intre acestea fiind o secventa
     // cu proprietatea ceruta
     sol=0;
     for( i=0 ; i<=7 ; i++)
       sol=sol+viz[i]*(viz[i]-1)/2;
     g << sol ;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1364)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1364/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1364/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)