C++で指定されたPrimeの倍数であるAPの最初の要素を検索します

コンセプト

等差数列の与えられた第1項（A）と共通の差（d）、および素数（P）に関して、私たちのタスクは、与えられたAPの最初の要素の位置を決定することです。素数P。

入力

A = 3, d = 4, P = 5

出力

3

説明

指定されたAPの第4項は、素数5の倍数です。

第1項=3

第2項=3+ 4 =7

第3項=3+ 2 * 4 =11

第4項=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に置き換えられているため）最後に両側でmodを取得-

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

出力

3