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

#include <bits/stdc++.h>
using namespace std;

ifstream cin("produs3.in");
ofstream cout("produs3.out");

int exp(int n , int x)
{
    int c = 0;
    while(n % x == 0)
    {
        n /= x;
        c++;
    }
    return c;

}

int main()
{
    int n , c2 = 0 , c3 = 0 , c5 = 0 , f[1001] = {0} , x;
    unsigned long long c = 0;
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x;
        c2 = (c2 + exp(x , 2)) % 2;
        c3 = (c3 + exp(x , 3)) % 2;
        c5 = (c5 + exp(x , 5)) % 2;
        f[4*c2 + 2*c3 + c5]++;
        //cout << 4*c2 + 2*c3 + c5 << endl;
    }
    c = f[0];
    for(int i = 0 ; i <= 10 ; i++)
        c = c + 1ll * f[i] * (f[i] - 1) / 2;
    cout << c;
}