अवधारणा
एक दिए गए प्रथम पद (A) और सार्व अंतर (d) के एक अंकगणितीय प्रगति के संबंध में, और एक अभाज्य संख्या (P), हमारा कार्य दी गई AP में उस पहले तत्व की स्थिति निर्धारित करना है जिसे दिए गए अभाज्य संख्या 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) + (P-A),
इस मामले में, P-A को एक गैर-ऋणात्मक संख्या माना जाता है
(क्योंकि A को A%P से प्रतिस्थापित किया जाता है जो P से छोटा है) अंत में दोनों तरफ मॉड लेकर −
((N-1)*d)%P = (P-A)%P या, ((N-1)d)%P = P-A
एक Y < P की गणना मान लें, ताकि (d*Y)%P = 1। अब, इस Y को d का P के संबंध में व्युत्क्रम मॉड्यूलो कहा जाता है।
अंत में उत्तर N है −
((Y*(P-A)) % P) + 1।
उदाहरण
<प्रि क्लास="प्रिटीप्रिंट नोट्रांसलेट">#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
