ধারণা
একটি গাণিতিক অগ্রগতির প্রদত্ত প্রথম পদ (A) এবং সাধারণ পার্থক্য (d) এবং প্রাইম সংখ্যা (P) এর ক্ষেত্রে, আমাদের কাজ হল প্রদত্ত এপি-তে প্রথম উপাদানটির অবস্থান নির্ধারণ করা যা প্রদত্তের একাধিক হিসাবে বিবেচনা করা হয়। মৌলিক সংখ্যা 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
অবশেষে উত্তর হল 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
