在 Python 中查找 AP 中第一个为给定素数倍数的元素

pythonserver side programmingprogramming更新于 2025/10/10 6:36:17

假设我们有一个 AP 系列的第一项 (A) 和公差 (d),并且我们还有一个素数 P,我们必须找到给定 AP 中第一个为给定素数 P 倍数的元素的位置。

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

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

  • 定义一个函数 get_pow() 。这将需要 x、y、p

  • ans := 1

  • x := x mod p

  • while 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

相关文章


有用资源