หาตำแหน่งพจน์แรกใน AP ที่เป็นตัวคูณของจำนวนเฉพาะ (Python)

โจทย์: กำหนดพจน์แรก A, ความต่างร่วม D ของ AP และจำนวนเฉพาะ P หาตำแหน่ง (0-indexed) ของพจน์แรกที่หาร P ลงตัว

ตัวอย่าง: A=3, D=4, P=5 → AP: 3,7,11,15,... → ตำแหน่ง 3 (พจน์ที่ 4)

คณิตศาสตร์: Modular Inverse

ต้องการหา n ที่น้อยที่สุด: A + nD ≡ 0 (mod P) → nD ≡ -A (mod P) → n ≡ -A × D⁻¹ (mod P)

D⁻¹ modulo P (P เป็นเฉพาะ) = D^(P-2) mod P (Fermat's Little Theorem)

อัลกอริทึม

1. A = A % P, D = D % P
2. ถ้า A == 0 → ตำแหน่ง 0
3. ถ้า D == 0 → ไม่มีคำตอบ (-1)
4. คำนวณ X = D^(P-2) mod P (modular inverse)
5. คำตอบ = (X × (P - A)) % P

ตัวอย่างโค้ด

def get_pow(x, y, p):
    ans = 1
    x = 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

print(get_nearest(3, 4, 5))  # 3

ผลลัพธ์

3

สรุป: ใช้ Modular Inverse (Fermat's Little Theorem) แก้สมการอนุพันธ์ modulo เฉพาะ O(log P) time สำหรับ fast exponentiation