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 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始