Tìm phần tử Đầu tiên trong AP là bội số của Số nguyên tố đã cho trong C ++

Khái niệm

Đối với số hạng đầu tiên đã cho (A) và hiệu số chung (d) của một Cấp số học, và số chuẩn (P), nhiệm vụ của chúng ta là xác định vị trí của phần tử đầu tiên trong AP đã cho, được coi là bội số của số nguyên tố P.

Đầu vào

A = 3, d = 4, P = 5

Đầu ra

Giải thích

Số hạng thứ tư của AP đã cho là bội số của số nguyên tố 5.

Kỳ đầu tiên =3

Kỳ thứ hai =3 + 4 =7

Kỳ hạn thứ ba =3 + 2 * 4 =11

Kỳ thứ tư =3 + 3 * 4 =15

Phương pháp

Giả sử thuật ngữ là AN. Do đó,

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

Vì vậy, người ta cho rằng AN là bội số của P. Như kết quả của điều này,

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

Ở đây, l là một hằng số.

Vì vậy, giả sử A là (A% P) và d là (d% P). Bây giờ, chúng ta có (N-1) * d =(l * P - A).

Với sự trợ giúp của việc cộng và trừ P trên RHS, chúng tôi thu được -

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

Trong trường hợp này, P-A được coi là một số không âm

(bởi vì A được thay thế bằng A% P nhỏ hơn P) Cuối cùng, hãy mod cả hai bên -

((N-1) * d)% P =(P-A)% P hoặc, ((N-1) d)% P =P-A

Giả sử tính toán một Y

Cuối cùng đáp án N là -

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

Ví dụ

#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;
}