Reszta z iloczynu

Potęgowanie modulo i jego zastosowania - Informatyka - liceum klasa 2, zakres rozszerzony (Python)

Reszta z dzielenia iloczynu zależy tylko od reszt czynników: `(a · b) mod m = ((a mod m) · (b mod m)) mod m`. Dlatego licząc `aⁿ mod m`, można po każdym mnożeniu brać resztę: liczby nie przekraczają `m²`, nawet gdy samo `aⁿ` ma tysiące cyfr. W Pythonie robi to wbudowane `pow(a, n, m)`.

def mod_power(a, n, m):
    result = 1
    a %= m
    while n > 0:
        if n % 2 == 1:
            result = result * a % m
        a = a * a % m
        n //= 2
    return result

a, n, m = 7, 2026, 1000
print(mod_power(a, n, m), pow(a, n, m), a ** n % m)
print("cyfr w 7 ** 2026:", len(str(a ** n)))

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

Wszystkie lekcje kursu Informatyka - liceum klasa 2, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.