แนวคิด
ได้รับพจน์แรก (A) และความต่างร่วม (d) ของลำดับเลขคณิต และจำนวนเฉพาะ (P) ให้หาตำแหน่งของพจน์แรกในลำดับเลขคณิตที่เป็นตัวคูณของจำนวนเฉพาะ P
อินพุต
A = 3, d = 4, P = 5
เอาต์พุต
3
คำอธิบาย
พจน์ที่ 4 ของลำดับเลขคณิตที่กำหนดเป็นตัวคูณของจำนวนเฉพาะ 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 ด้านขวา ได้:
(N-1)*d = P(l-1) + (P-A)
ที่นี่ P-A เป็นจำนวนไม่ติดลบ (เพราะ A ถูกแทนที่ด้วย A%P ซึ่งน้อยกว่า P) สุดท้ายหา mod ทั้งสองข้าง:
((N-1)*d)%P = (P-A)%P หรือ ((N-1)d)%P = P-A
หา Y < P ที่ทำให้ (d*Y)%P = 1 Y นี้เรียกว่า modulo inverse ของ d เทียบกับ P
คำตอบ N สุดท้ายคือ:
((Y*(P-A)) % P) + 1
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
// ฟังก์ชันวนคำนวณ (x1^y1)%p1 ใน O(log y1)
int power(int x1, int y1, int p1) {
// เริ่มต้นผลลัพธ์
int res1 = 1;
// อัปเดต x หากมากกว่าหรือเท่ากับ p
x1 = x1 % p1;
while (y1 > 0) {
// หาก y1 คี่ คูณ x1 กับผลลัพธ์
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
