मान लीजिए हमारे पास एक AP श्रृंखला का पहला पद (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।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
एक फ़ंक्शन get_pow() परिभाषित करें। यह x, y, p लेगा
ans := 1
x := x mod p
जब y > 0, करें
यदि y AND 1 शून्येतर है, तो
ans := (ans * x) mod p
y := y/2
x := (x * x) mod p
ans वापस करें
मुख्य विधि से, निम्नलिखित करें -
A := A mod P
D := D mod P
यदि A, 0 के समान है, तो
0 वापस करें
अन्यथा जब D, 0 के समान है, तो
-1 वापस करें
अन्यथा,
X := get_pow(D, P - 2, P)
(X * (P - A)) mod P वापस करें
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
def get_pow(x, y, p) : ans = 1 x = x % p while y > 0 : if y & 1 : ans = (ans * x) % p y = y >> 1 x = (x * x) % p return ans def get_nearest(A, D, P) : A %= P D %= P if A == 0 : return 0 elif D == 0 : return -1 else : X = get_pow(D, P - 2, P) return (X * (P - A)) % P A = 3 D = 4 P = 5 print(get_nearest(A, D, P))
इनपुट
A = 3 D = 4 P = 5
आउटपुट
3
