3474 - Squary

Cerinţa

Se dau n numere naturale. Aflați numărul subsecventelor care au produsul pătrat perfect.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul subsecventelor care respectă condiția. În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu respecta cerintele impuse." , iar daca se indeplinesc, se afiseaza mesajul "Datele de intrare respecta cerintele impuse."

Restricţii şi precizări

• 1 ≤ n ≤ 100.000
• cele n numere citite vor fi mai mici decât 300

Exemplul 1

Intrare

5
1 2 4 8 16

Ieșire

Datele de intrare respecta cerintele impuse.
7

Exemplul 2

Intrare

3
1 2 500

Ieșire

Datele de intrare nu respecta cerintele impuse.

Rezolvare

from math import isqrt

def numar_subsecvente_patrat_perfect(n, numere):
    numar_subsecvente = 0
    prefixe_produs = [1]

    for numar in numere:
        prefixe_produs.append(prefixe_produs[-1] * numar)

    for i in range(n):
        for j in range(i, n):
            produs = prefixe_produs[j + 1] // prefixe_produs[i]

            if isqrt(produs) ** 2 == produs:
                numar_subsecvente += 1

    return numar_subsecvente

if __name__ == "__main__":
    try:
        n = int(input())
        numere = list(map(int, input().split()))

        if 1 <= n <= 100000 and len(numere) == n and all(1 <= numar <= 300 for numar in numere):
            print("Datele de intrare respecta cerintele impuse.")
            rezultat = numar_subsecvente_patrat_perfect(n, numere)
            print(rezultat)
        else:
            print("Datele de intrare nu respecta cerintele impuse.")

    except ValueError:
        print("Datele de intrare nu respecta cerintele impuse.")