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

สมมติว่าเรามีตัวเลขสองตัว n และ m เราต้องหาเศษที่เหลือหลังจากหาร n จำนวน 1s ด้วย m.

ดังนั้น หากอินพุตเท่ากับ n =4 m =27 เอาต์พุตจะเป็น 4 เพราะ 1111 mod 27 =4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดฟังก์ชัน util() นี่จะใช้เวลา x, n, m

• y :=1
• ในขณะที่ n> 0, ทำ
  • ถ้า n เป็นเลขคี่
    • y :=(y * x) mod m
  • x :=(x * x) mod m
    • n :=ชั้นของ n/2
• คืน y

จากวิธีหลัก return 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))

อินพุต

4, 27

ผลลัพธ์

4