সি++-এ দিয়ে রেঞ্জে x² ≡ 1 (mod p) সমাধানের সংখ্যা গণনা

দুটি ইন্টিজার x এবং p দেওয়া আছে। লক্ষ্য হল সমীকরণ x² = 1 (mod p) এর সমাধান সংখ্যা বের করা যাতে x [1,N] রেঞ্জে থাকে।

1 থেকে N পর্যন্ত ট্রাভার্স করা হয়। প্রতিটি সংখ্যাকে x ধরে (x*x)%p==1 কিনা চেক করা হয়। হলে count বাড়ানো হয়।

উদাহরণ

ইনপুট: n=5, p=2

আউটপুট: সমাধান সংখ্যা: ৩

ব্যাখ্যা: ১ থেকে ৫ পর্যন্ত: 1²%2=1, 2²%2=0, 3²%2=1, 4²%2=0, 5²%2=1। মোট ৩টি সমাধান।

ইনপুট: n=3, p=4

আউটপুট: সমাধান সংখ্যা: ২

ব্যাখ্যা: ১ থেকে ৩ পর্যন্ত: 1²%4=1, 2²%4=0, 3²%4=1। মোট ২টি সমাধান।

অ্যাপ্রোচ

n এবং p দুটি ভেরিয়েবল।
solutionsCount(int n, int p) ফাংশন n এবং p গ্রহণ করে x²%p==1 সমীকরণের সমাধান সংখ্যা রিটার্ন করে।
for লুপে x=1 থেকে x<=n পর্যন্ত: (x*x)%p == 1 হলে count++।

উদাহরণ কোড

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

int solutionsCount(int n, int p) {
    int count = 0;
    for (int x = 1; x <= n; x++) {
        if ((x * x) % p == 1) {
            ++count;
        }
    }
    return count;
}

int main() {
    int n = 8, p = 3;
    cout << "Number of solutions :" << solutionsCount(n, p);
    return 0;
}

আউটপুট

Number of solutions : 6