在Python中查找算术级数中第一个是给定素数倍数的元素

假设我们有算术级数的第一个项 (A) 和公差 (d)，以及一个素数 P，我们需要找到给定算术级数中第一个是给定素数 P 的倍数的元素的位置。

因此，如果输入为 A = 3, D = 4, P = 5，则输出将为 3，因为给定算术级数的第四项是素数 5 的倍数。所以，第一项 = 3，第二项 = 3+4 = 7，第三项 = 3+2*4 = 11，第四项 = 3+3*4 = 15。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数 get_pow()。它将接收 x, y, p。

  • ans := 1

  • x := x mod p

  • 当 y > 0 时，执行：

    • 如果 y AND 1 非零，则

      • ans := (ans * x) mod p

    • y := y/2

    • x := (x * x) mod p

  • 返回 ans

  • 在主方法中，执行以下操作：

  • A := A mod P

  • D := D mod P

  • 如果 A 等于 0，则

    • 返回 0

  • 否则，如果 D 等于 0，则

    • 返回 -1

  • 否则，

    • X := get_pow(D, P - 2, P)

    • 返回 (X *(P - A)) mod P

示例

让我们看下面的实现来更好地理解：

 在线演示

def get_pow(x, y, p) :
   ans = 1
   x = x % p
   while y > 0 :
      if y & 1 :
         ans = (ans * x) % p
      y = y >> 1
      x = (x * x) % p
   return ans
def get_nearest(A, D, P) :
   A %= P
   D %= P
   if A == 0 :
      return 0
   elif D == 0 :
      return -1
   else :
      X = get_pow(D, P - 2, P)
      return (X * (P - A)) % P

A = 3
D = 4
P = 5
print(get_nearest(A, D, P))

输入

A = 3 D = 4 P = 5

输出

3

更新于：2020年8月25日

59 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告