โปรแกรมคำนวณโมดุลอของตัวเลขที่ต่อเนื่อง n ครั้งใน Python

ได้รับตัวเลข A ต้องการสร้างตัวเลขใหญ่ X โดยการต่อ A ติดกัน n ครั้ง แล้วหา X mod m

ตัวอย่าง: A=15, n=3, m=8 → X=151515, 151515 mod 8 = 3

ขั้นตอนการแก้ปัญหา

1. หาก A=0 คืนค่า 0
2. ให้ c = 10^{จำนวนหลักของ A}
3. ใช้สูตรอนุกรมเรขาคณิต: X = A * (c^n - 1) / (c - 1)
4. คำนวณโมดุลอโดยใช้คุณสมบัติ: (c^n - 1) / (c - 1) mod m สามารถคำนวณได้โดยใช้ modulo (c-1)*m

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

def solve(A, n, m):
    if A == 0:
        return 0
    c = 10 ** len(str(A))
    d = c - 1
    newmod = d * m
    val = (pow(c, n, newmod) - 1) % newmod
    an = (A * val) % newmod
    return an // d

# ทดสอบ
A = 15
n = 3
m = 8
print(solve(A, n, m))  # ผลลัพธ์: 3

อินพุตตัวอย่าง

15, 3, 8

เอาต์พุตตัวอย่าง

3