แนวคิด
ด้วยความเคารพของเทอมแรกที่กำหนด (A) และความแตกต่างร่วมกัน (d) ของความก้าวหน้าทางคณิตศาสตร์และจำนวนเฉพาะ (P) หน้าที่ของเราคือกำหนดตำแหน่งขององค์ประกอบแรกใน AP ที่กำหนด ซึ่งถือว่าเป็นผลคูณของค่าที่กำหนด เลขเฉพาะ ป.
อินพุต
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)
ด้วยความช่วยเหลือของการบวกและลบ P บน RHS เราได้รับ -
(N-1)*d =P(l-1) + (PA),
ในกรณีนี้ P-A จะถือเป็นตัวเลขที่ไม่ติดลบ
(เพราะ A ถูกแทนที่ด้วย A%P ซึ่งเล็กกว่า P) ในที่สุดก็ทำการดัดแปลงทั้งสองด้าน -
((N-1)*d)%P =(PA)%P หรือ ((N-1)d)%P =P-A
สมมติว่าคำนวณ 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
