C++-এ (A ≤ N, B ≤ N) যাতে gcd(A, B) = B হয় এমন জোড়া সংখ্যা গণনা

আমাদের একটি ইনপুট N দেওয়া আছে। লক্ষ্য হলো A, B এর সব জোড়া বের করা যাতে ১ ≤ A ≤ N, ১ ≤ B ≤ N এবং GCD(A, B) = B। অর্থাৎ সব জোড়ার গ্রেটেস্ট কমন ডিভাইজর (GCD) হবে B।

উদাহরণ দিয়ে বুঝি

ইনপুট − N=5

আউটপুট − gcd(A, B) = B হয় এমন জোড়া সংখ্যা: ১০

ব্যাখ্যা − জোড়া গুলো: (1,1), (2,1), (3,1), (4,1), (5,1), (2,2), (3,3), (4,2), (4,4), (5,5)। মোট ১০।

ইনপুট − N=50

আউটপুট − gcd(A, B) = B হয় এমন জোড়া সংখ্যা: ২০৭

ব্যাখ্যা − জোড়া গুলো: (1,1), (2,1), (3,1)... (50,1), (2,2), (3,3)... (50,50) এবং (4,2), (6,3), (8,2), (8,4)... (50,25)। মোট ২০৭।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

এই সমস্যা সমাধানের দুটি পদ্ধতি: নেভ הפשט এবং দক্ষ পদ্ধতি।

নেভ הפשט পদ্ধতি

• ইন্টিজার N ইনপুট নিন।
• GCD(int A, int B) ফাংশন দুটি ইন্টিজারের GCD রিকার্সিভলি রিটার্ন করে।
• count_pairs(int N) ফাংশন N নিয়ে বৈধ জোড়া কাউন্ট রিটার্ন করে।
• প্রাথমিক count=0।
• দুটি নেস্টেড লুপ: i=1 থেকে N (A-এর জন্য), j=1 থেকে N (B-এর জন্য)।
• জোড়া (i,j) বানিয়ে GCD(i,j) কল করুন। ফলাফল j সমান হলে count++।
• count রিটার্ন করুন।

দক্ষ পদ্ধতি (Efficient Approach)

GCD(a,b)=b মানে a সবসময় b-র গুণিতক (multiple)। ১ ≤ b ≤ N এর সব গুণিতক যেগুলো N-এর চেয়ে ছোট বা সমান, সেগুলো জোড়া বানাবে। একটি সংখ্যা i-এর জন্য N-এর চেয়ে ছোট বা সমান গুণিতক সংখ্যা floor(N/i)।

• Count_pairs(int N) ফাংশন N নিয়ে বৈধ জোড়া কাউন্ট রিটার্ন করে।
• প্রাথমিক count=0, temp=N, i=1।
• while(i <= N):
  • j = N / temp (গুণিতকের লিমিট)।
  • বর্তমান i-এর জোড়া সংখ্যা: temp * (j - i + 1)। count-এ যোগ করুন।
  • i = j + 1 (পরবর্তী B-এর জন্য)।
  • temp = N / i (পরবর্তী ইটারেশনের জন্য)।
• count রিটার্ন করুন।

উদাহরণ (নেভ הפשט পদ্ধতি)

#include <iostream>
using namespace std;

int GCD(int A, int B) {
    if (A == 0) return B;
    if (B == 0) return A;
    if (A == B) return A;
    if (A > B) return GCD(A - B, B);
    return GCD(A, B - A);
}

int count_pairs(int N) {
    int count = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (GCD(i, j) == j) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int N = 4;
    cout << "Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: " << count_pairs(N);
    return 0;
}

আউটপুট

Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: 8

উদাহরণ (দক্ষ পদ্ধতি)

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

int Count_pairs(int N) {
    int count = 0;
    int temp = N;
    int i = 1;
    while (i <= N) {
        int j = N / temp;
        count += temp * (j - i + 1);
        i = j + 1;
        temp = N / i;
    }
    return count;
}

int main() {
    int N = 4;
    cout << "Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: " << Count_pairs(N);
    return 0;
}

আউটপুট

Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: 8