Tìm phần tử đầu tiên trong AP là bội số của Prime đã cho trong Python

Giả sử chúng ta có một số hạng đầu tiên (A) và hiệu chung (d) của một chuỗi AP, và chúng ta cũng có một số nguyên tố P, chúng ta phải tìm vị trí của phần tử đầu tiên trong AP đã cho, là bội số của số nguyên tố P đã cho.

Vì vậy, nếu đầu vào là A =3, D =4, P =5, thì đầu ra sẽ là 3 vì số hạng thứ tư của AP đã cho là bội số của số nguyên tố 5. Vì vậy, số hạng đầu tiên =3, số hạng thứ hai =3 + 4 =7, số hạng thứ ba =3 + 2 * 4 =11 và số hạng thứ tư =3 + 3 * 4 =15.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm get_pow (). Điều này sẽ mất x, y, p

• ans:=1

• x:=x mod p

• trong khi y> 0, thực hiện

  • nếu y VÀ 1 khác 0 thì

    • ans:=(ans * x) mod p

  • y:=y / 2

  • x:=(x * x) mod p

• trả lại ans

• Từ phương thức chính, thực hiện như sau -

• A:=A mod P

• D:=D mod P

• nếu A giống 0 thì

  • trả về 0

• ngược lại khi D giống 0 thì

  • trả về -1

• nếu không,

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

  • return (X * (P - A)) mod P

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

A = 3 D = 4 P = 5

Đầu ra

3