Chương trình tìm phần dư sau khi chia n số 1 cho m trong Python

Giả sử chúng ta có hai số n và m. Ta phải tìm phần còn lại sau khi chia n số 1 cho m.

Vì vậy, nếu đầu vào là n =4 m =27, thì đầu ra sẽ là 4, bởi vì 1111 mod 27 =4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Định nghĩa một hàm dùng (). Điều này sẽ mất x, n, m

• y:=1
• while n> 0, do
  • nếu n lẻ, thì
    • y:=(y * x) mod m
  • x:=(x * x) mod m
    • n:=tầng của n / 2
• trả lại y

Từ tầng trả về của phương pháp chính là (dùng (10, n, 9 * m) / 9)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

4, 27

Đầu ra

4