# PBinfo #3043 – cub3 – Rezolvare C++

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

## Enunț

Ionel are de rezolvat o nouă problemă. El trebuie să construiască un șir de N numere naturale. Numerele din șir pot avea ca divizori primi doar numere prime de o cifră. După construirea șirului, Ionel a constatat că există subsecvențe în șir pentru care produsul elementelor este cubul unui număr natural.

Cerința
Ionel vrea să determine numărul subsecvențelor din șirul construit care au produsul elementelor o valoare ce este cubul unui număr natural.

Date de intrare
Fișierul de intrare cub.in va conține pe prima linie numărul natural N, iar pe linia următoare se vor afla N numere naturale separate prin câte un spațiu, elementele șirului construit de Ionel.

Date de ieșire
Fișierul de ieșire cub.out va conține pe prima linie un număr natural reprezentând numărul subsecvenţelor din șirul construit care au produsul elementelor egal cu o valoare ce este cubul unui număr natural.

Restricții și precizări

N și elemente șirului sunt numere naturale din intervalul [2, 1.000.000].
Prin subsecvenţă a unui șir se înțelege o succesiune de unul sau mai mulți termeni din șir aflați pe poziții consecutive.
Pentru teste în valoare de 20 de puncte, N ≤ 1.000.
Pentru teste în valoare de 40 de puncte, N ≤ 10.000.

Exemplu:
cub.in

8
15 3 5 15 7 63 21 125
cub.out

6
Explicație
Sunt 6 subsecvențe în șir cu produsul elementelor egal cu o valoare care este cubul unui număr natural:
15 3 5 15
7 63 21
125
15 3 5 15 7 63 21
7 63 21 125
15 3 5 15 7 63 21 125

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cub.in");
ofstream fout("cub.out");
int i, j, nr, n, x, mul, crtState[4], states[100];
long long sol;
const int divs[] = {2, 3, 5, 7};
int convert() {
    return crtState[3] * 3 * 3 * 3 + crtState[2] * 3 * 3 + crtState[1] * 3 + crtState[0];
}
int main()
{
    fin >> n;
    for (i = 1 ; i <= n ; i++) {
        fin >> x;
        for (j = 0 ; j < 4 ; j++) {
            nr = 0;
            while (x % divs[j] == 0) {
                nr++;
                x /= divs[j];
                crtState[j]++;
            }
            crtState[j] %= 3;
        }
        states[convert()]++;
    }
    states[0]++;
    for (i = 0 ; i < 81 ; i++)
        sol += states[i] * (states[i] - 1) / 2;
    fout << sol;
    return 0;
}
```

## Resurse

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