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

Z时代
2024-01-10
分类：综合

概念

关于算术级数的给定的第一项(A)和共同差(d)，以及质数(P)，我们的任务是确定给定AP中第一个元素的位置，该位置被视为A的倍数。给定素数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)+(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;
}