关于算术级数的给定的第一项(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