Chương trình tìm dư khi chia số gồm n chữ số 1 cho m trong Python

Cho n, m. Tìm (111...1 n lần) mod m. Dùng lũy thừa modulo nhanh.

Thuật toán

• Số n chữ số 1 = (10^n - 1) / 9.
• Tính 10^n mod (9*m) bằng lũy thừa nhanh (binary exponentiation).
• Kết quả = (pow(10, n, 9*m) - 1) // 9 mod m (hoặc chia nguyên sau khi trừ 1).

Ví dụ

def util(x, n, m):
    y = 1
    while n > 0:
        if n & 1:
            y = (y * x) % m
        x = (x * x) % m
        n >>= 1
    return y

def solve(n, m):
    return util(10, n, 9 * m) // 9

print(solve(4, 27))  # Output: 4 (1111 % 27 = 4)

Giải thích

1111 mod 27 = 4.