Python에서 주어진 Prime의 배수인 AP의 첫 번째 요소 찾기

AP 급수의 첫 번째 항(A)과 공차(d)가 있고 소수 P도 있다고 가정하면 첫 번째 요소의 위치를 ​​찾아야 합니다. 주어진 소수 P의 배수인 주어진 AP에서.

따라서 입력이 A =3, D =4, P =5와 같으면 주어진 AP의 네 번째 항이 소수 5의 배수이므로 출력은 3이 됩니다. 따라서 첫 번째 항 =3, 두 번째 항 =3+4 =7, 세 번째 항 =3+2*4 =11 및 네 번째 항 =3+3*4 =15.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• get_pow() 함수를 정의합니다. x, y, p

  가 필요합니다.

• 답변 :=1

• x :=x 모드 p

• y> 0일 때 수행

  • y AND 1이 0이 아니면

    • ans :=(ans * x) 모드 p

  • y :=y/2

  • x :=(x * x) 모드 p

• 반환

• 기본 방법에서 다음을 수행하십시오 -

• A :=A 모드 P

• D :=D 모드 P

• A가 0과 같으면

  • 0 반환

• 그렇지 않으면 D가 0과 같을 때

  • 반환 -1

• 그렇지 않으면

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

  • return(X *(P - A)) 모드 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