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

<시간/>

컨셉

산술 진행의 주어진 첫 번째 항(A)과 공차(d), 그리고 소수(P)와 관련하여 우리의 임무는 주어진 AP의 첫 번째 요소의 위치를 결정하는 것입니다. 소수 P.

입력

A = 3, d = 4, P = 5

출력

설명

주어진 AP의 네 번째 항은 소수 5의 배수입니다.

첫 번째 용어 =3

두 번째 용어 =3+4 =7

세 번째 항 =3+2*4 =11

네 번째 항 =3+3*4 =15

방법

항이 AN이라고 가정합니다. 그 결과,

AN =(A + (N-1)*d)

따라서 AN은 P의 배수로 주어집니다. 이에 따라

A + (N-1)*d =l*P

여기서 l은 상수입니다.

따라서 A는 (A % P)이고 d는 (d % P)라고 가정합니다. 이제 (N-1)*d =(l*P – A)가 있습니다.

RHS에서 P를 더하거나 빼서 다음을 얻습니다. -

(N-1)*d =P(l-1) + (P-A),

이 경우 P-A는 음수가 아닌 숫자로 처리됩니다.

(A가 P보다 작은 A%P로 대체되기 때문에)드디어 양쪽에서 모드를 사용 -

((N-1)*d)%P =(P-A)%P 또는, ((N-1)d)%P =P-A

(d*Y)%P =1이 되도록 Y

마지막으로 답 N은 -

입니다.

((Y*(P-A)) % P) + 1.

예시

#include <bits/stdc++.h>
using namespace std;
// Shows iterative Function to calculate
// (x1^y1)%p1 in O(log y1) */
int power(int x1, int y1, int p1){
   // Used to initialize result
   int res1 = 1;
   // Used to update x if it is more than or
   // equal to p
   x1 = x1 % p1;
   while (y1 > 0) {
      // It has been seen that if y1 is odd, multiply x1 with
      result
      if (y1 & 1)
         res1 = (res1 * x1) % p1;
         // y1 must be even now
      y1 = y1 >> 1; // y1 = y1/2
      x1 = (x1 * x1) % p1;
   }
   return res1;
}
// Shows function to find nearest element in common
int NearestElement1(int A, int d, int P){
   // Shows base conditions
   if (A == 0)
      return 0;
   else if (d == 0)
      return -1;
   else {
      int Y = power(d, P - 2, P);
      return (Y * (P - A)) % P;
   }
}
// Driver code
int main(){
   int A = 3, d = 4, P = 5;
   // Used to module both A and d
   A %= P;
   d %= P;
   // Shows function call
   cout << NearestElement1(A, d, P);
   return 0;
}