Tìm phần tử đầu tiên của cấp số cộng là bội của số nguyên tố trong Python

Cho số hạng đầu A, công sai D của cấp số cộng (AP), và số nguyên tố P. Tìm vị trí (chỉ số 0-based) của phần tử đầu tiên trong AP là bội của P.

Ví dụ: A=3, D=4, P=5 → Số hạng thứ 3 (0-based) = 3+3×4=15 chia hết 5 → Trả về 3.

Thuật toán dùng nghịch đảo modulo

1. Cần tìm nhỏ nhất k ≥ 0 sao cho A + k·D ≡ 0 (mod P) → k·D ≡ -A (mod P).
2. Vì P là nguyên tố, D có nghịch đảo modulo P: D⁻¹ ≡ D^(P-2) (mod P) (Fermat).
3. k ≡ D⁻¹ · (P - A) (mod P).
4. Trả về k.

Ví dụ code

def get_pow(x, y, p):
    ans = 1
    x %= p
    while y > 0:
        if y & 1:
            ans = (ans * x) % p
        y >>= 1
        x = (x * x) % p
    return ans

def get_nearest(A, D, P):
    A %= P
    D %= P
    if A == 0:
        return 0
    elif D == 0:
        return -1
    else:
        X = get_pow(D, P - 2, P)
        return (X * (P - A)) % P

A = 3
D = 4
P = 5
print(get_nearest(A, D, P))

Input

A = 3, D = 4, P = 5

Output

3