0982 - Puteri1

Cerință

Se dau n numere naturale. Aflați câte dintre acestea se pot scrie ca sumă de puteri distincte ale unui număr natural k.

Date de intrare

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

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse." și programul va afișa pe ecran numărul de numere din șirul dat care se pot scrie ca sumă de puteri distincte ale lui k. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

Restricții de precizări

• 1 ⩽ n ⩽ 10000

• 2 ⩽ k ⩽ 10

• cele n numere citite vor fi mai mici decât 1.000.000

Exemplu

Exemplul 1

Intrare

5

3

6

37

12

9

5

Ieșire

Datele introduse corespund restricțiilor impuse.

3

Rezolvare

Rezolvare ver. 1

def validare(n, k):
    # Funcție pentru validarea valorilor n și k
    # Returnează True dacă valorile sunt valide, False în caz contrar
    return 1 <= int(n) <= 100_000 and 2 <= int(k) <= 10


def numar_puteri_distincte(n, k):
    # Funcție pentru calcularea numărului de puteri distincte
    nr = 0
    for i in range(1, n + 1):
        x = int(input("numbers:")) # Solicitare valoare de la utilizator pentru fiecare iterație
        c = 1
        while x != 0:
            if x % k > 1: # Verificare dacă restul împărțirii lui x la k este mai mare decât 1
                c = 0 # Dacă da, setează c la 0 și iesi din while
                break
            x //= k # Împărțirea lui x la k și reținerea partea întreagă
        if c:
            nr += 1 # Dacă c este nenul, incrementarea numărului de puteri distincte
    return nr


if __name__ == "__main__":
    n = input("n: ") # Solicitare valoare pentru n
    k = input("k: ") # Solicitare valoare pentru k
    if validare(n, k): # Verificare validitate valori n și k utilizând funcția validare()
        n, k = int(n), int(k) # Convertirea valorilor n și k la tipul int
        x = numar_puteri_distincte(n, k) # Apelarea funcției numar_puteri_distincte() pentru a calcula numărul de puteri distincte
        print("Datele introduse corespund restricțiilor impuse.")
        print(x) # Afișare rezultat
    else:
        print("Datele introduse nu corespund restricțiilor impuse.")