3043 - cub3

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 input.txt 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 output.txt 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].

Exemplul 1

input.txt:

8

15 3 5 15 7 63 21 125

output.txt:

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

Exemplul 2

input.txt:

99999999999

15 3 5 15 7 63 21 125

Output:

Input-ul nu convine conditiilor

Rezolvare

import math

def verificare(n):
    if not(2<=n<=1000000):
        print("Input-ul nu convine conditiilor")
        exit()

def convert():
    return crtState[3] * 3 * 3 * 3 + crtState[2] * 3 * 3 + crtState[1] * 3 + crtState[0]

fin = open("input.txt", "r")
fout = open("output.txt", "w")

n = int(fin.readline())
verificare(n)
i, j, nr, x, mul, sol = 0, 0, 0, 0, 0, 0
crtState = [0] * 4
states = [0] * 100
divs = [2, 3, 5, 7]

l=list(map(int, fin.readline().split()))

for _ in range(1, n + 1):
    x = l[i-1]

    for j in range(4):
        nr = 0
        while x % divs[j] == 0:
            nr += 1
            x //= divs[j]
            crtState[j] += 1

        crtState[j] %= 3

    states[convert()] += 1

states[0] += 1

for i in range(81):
    sol += states[i] * (states[i] - 1) // 2

fout.write(str(int(math.sqrt(sol))))

fin.close()
fout.close()