โปรแกรมหาเศษจากการหาร n ตัวเลข 1 ด้วย m ใน Python

กำหนด n และ m หาเศษจากการหารตัวเลขที่ประกอบด้วย n ตัวเลข 1 ด้วย m

เช่น n = 4, m = 27 ผลลัพธ์คือ 4 เพราะ 1111 mod 27 = 4

วิธีแก้ปัญหา

กำหนดฟังก์ชัน util() รับ x, n, m

• y := 1
• while n > 0
  • ถ้า n เป็นคี่ y := (y * x) mod m
  • x := (x * x) mod m
  • n := floor(n/2)
• คืนค่า y

จาก main method คืนค่า floor(util(10, n, 9 * m) / 9)

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

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

n = 4
m = 27
print(solve(n, m))

Input

4, 27

Output

4