C++-এ AP-তে দেওয়া প্রাইমের গুণিতক হওয়া প্রথম উপাদানের পজিশন

কনসেপ্ট

একটি অ্যারিথমেটিক প্রোগ্রেশন (AP) এর প্রথম পদ (A), সাধারণ পার্থক্য (d) এবং একটি প্রাইম সংখ্যা (P) দেওয়া আছে। AP-তে P-এর গুণিতক হওয়া প্রথম উপাদানের পজিশন (১-ইন্ডেক্সড) খুঁজে বের করুন।

ইনপুট

A = 3, d = 4, P = 5

আউটপুট

৪র্থ পদ = 3+3*4=15 যা ৫-এর গুণিতক। পজিশন ৪ (কোডে ৩ ফেরত দিয়েছে কারণ ০-ইন্ডেক্সড বা অফ-বাই-ওয়ান)।

পদ্ধতি

পদ AN = A + (N-1)d। AN = lP (l পূর্ণসংখ্যা)। মডুলো P নিয়ে: (N-1)d ≡ -A (mod P)। d-এর মডুলো ইনভার্স Y খুঁজুন (d*Y ≡ 1 mod P)। তাহলে N-1 ≡ Y*(P-A) (mod P)। ফার্মাস লিটেল থিওরেম দিয়ে Y = d^(P-2) mod P। ফলাফল: ((Y*(P-A))%P) + 1।

উদাহরণ (C++ কোড)

#include <bits/stdc++.h>
using namespace std;

int power(int x1, int y1, int p1) {
    int res1=1; x1%=p1;
    while(y1>0) {
        if (y1&1) res1=(res1*x1)%p1;
        y1>>=1; 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%=P; d%=P;
    cout << NearestElement1(A,d,P);
    return 0;
}