Python 程式：求 n 個 1 除以 m 的餘數

假設我們有兩個數字 n 和 m。我們需要找到 n 個 1 除以 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

在主方法中，返回 (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

Arnab Chakraborty

更新時間： 2021年10月25日

417 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始