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

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema cub3:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3043 cub3

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3043 cub3 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3043 cub3