在AP中查找First元素,它是C ++中给定Prime的倍数

概念

关于算术级数的给定的第一项(A)和共同差(d),以及质数(P),我们的任务是确定给定AP中第一个元素的位置,该位置被视为A的倍数。给定素数P。

输入值

A = 3, d = 4, P = 5

输出结果

3

说明

给定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)+(PA),

在这种情况下,PA被视为非负数

(因为A被小于P的A%P代替)最后在两边取mod-

((N-1)* d)%P =(PA)%P或((N-1)d)%P = PA

假设计算Y <P,因此(d * Y)%P =1。现在,将该Y称为d相对于P的逆模。

最后答案N是-

(((Y *(PA))%P)+ 1。

示例

#include <bits/stdc++.h>
using namespace std;
//显示要计算的迭代函数
//O(log y1)中的(x1 ^ y1)%p1 * /
int power(int x1, int y1, int p1){
   //用于初始化结果
   int res1 = 1;
   //,则用于更新x
   //等于p-
   x1 = x1 % p1;
   while (y1 > 0) {
      //已经看到,如果y1是奇数,则将x1乘以
      result
      if (y1 & 1)
         res1 = (res1 * x1) % p1;
         //y1必须是现在
      y1 = y1 >> 1; // y1 = y1/2
      x1 = (x1 * x1) % p1;
   }
   return res1;
}
//显示功能以查找共同点中最接近的元素
int NearestElement1(int A, int d, int P){
   //显示基本条件
   if (A == 0)
      return 0;
   else if (d == 0)
      return -1;
   else {
      int Y = power(d, P - 2, P);
      return (Y * (P - A)) % P;
   }
}
//驱动程式码
int main(){
   int A = 3, d = 4, P = 5;
   //用于模块A和d-
   A %= P;
   d %= P;
   //显示函数调用
   cout << NearestElement1(A, d, P);
   return 0;
}

输出结果

3