3.5 Rozwiązywalne trójki w pliku przykładowym

Matura pokazowa marzec 2022 - Matura z informatyki: arkusze krok po kroku (Python)

Zadanie 3.5 (2 pkt): dla ilu trójek (M, a, b) istnieje x od 0 do M - 1, dla którego a^x mod M = b. Szybkie potęgowanie dla każdego x osobno byłoby marnotrawstwem: kolejna potęga to poprzednia razy a (modulo M), więc jeden obrót pętli to jedno mnożenie. Pętla kończy się `break` przy pierwszym trafieniu. Dla pliku przykładowego: 4.

rows = []
with open("liczby_przyklad.txt") as f:
    for line in f:
        M, a, b = map(int, line.split())
        rows.append((M, a, b))

# 3.5 kolejne potęgi a^0, a^1, ..., a^(M-1) modulo M: każda z poprzedniej jednym mnożeniem
solvable = 0
for M, a, b in rows:
    value = 1 % M  # a^0 mod M
    for x in range(M):
        if value == b:
            solvable = solvable + 1
            break
        value = value * a % M

print("3.5", solvable)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Matura z informatyki: arkusze krok po kroku·Zaloguj się, aby zapisać postęp na koncie.