C++ में उन जोड़े (A ≤ N, B ≤ N) की गिनती जिनका gcd(A, B) = B हो

हमें एक इनपुट N दिया गया है। लक्ष्य A, B के उन सभी जोड़े ढूंढना है जैसे कि 1 ≤ A ≤ N और 1 ≤ B ≤ N और GCD(A, B) = B हो। सभी जोड़े का महत्तम समापवर्तक B है।

उदाहरण सहित समझ

इनपुट - N=5

आउटपुट - जोड़े (A ≤ N, B ≤ N) जिनका gcd(A, B) = B है: 10

व्याख्या

जोड़े (A ≤ N, B ≤ N) जिनका gcd(A, B) = B है:
(1,1), (2,1), (3,1), (4,1), (5,1), (2,2), (3,3), (4,2), (4,4), (5,5). कुल 10।

इनपुट - N=50

आउटपुट - जोड़े (A ≤ N, B ≤ N) जिनका gcd(A, B) = B है: 207

व्याख्या

जोड़े (A ≤ N, B ≤ N) जिनका gcd(A, B) = B है:
(1,1), (2,1), (3,1), (4,1), (5,1).... (50,1)
(2,2), (3,3), (4,4).... (50,50)
इसी तरह अन्य जोड़े जैसे (4,2), (6,3), (8,2), (8,4)..... (50,25). कुल 207

प्रोग्राम में उपयोग किया गया दृष्टिकोण

दिए गए समस्या को हल करने के लिए कई दृष्टिकोण हो सकते हैं यानी सामान्य दृष्टिकोण और कुशल दृष्टिकोण। तो आइए पहले सामान्य दृष्टिकोण देखते हैं।

• इनपुट के रूप में एक पूर्णांक N लें।
• फंक्शन GCD(int A, int B) दो पूर्णांक लेता है और A और B का महत्तम समापवर्तक लौटाता है। यह रिकर्सिवली gcd की गणना करता है।
• यदि A या B में से कोई 0 है तो दूसरा लौटाएँ। यदि दोनों समान हैं तो दोनों में से कोई भी मान लौटाएँ। यदि A > B तो GCD(A-B, B) लौटाएँ। यदि B बड़ा है, तो GCD(B-A, A) लौटाएँ। अंत में हमें gcd मान प्राप्त होता है।
• फंक्शन count_pairs(int N) N लेता है और ऐसे जोड़े की संख्या लौटाता है जिनमें जोड़े (A,B) में B, gcd है और दोनों रेंज [1,N] में हैं।
• प्रारंभिक मान count = 0 लें ऐसे जोड़े की संख्या के लिए।
• जोड़े के प्रत्येक मान के लिए, A के लिए i=1 से i=N तक फॉर लूप चलाएँ और नेस्टेड फॉर लूप j=1 से j=N तक B के लिए चलाएँ।
• एक जोड़ा (i,j) बनाएं और GCD(i,j) में पास करें। यदि परिणाम j के बराबर है। काउंट बढ़ाएँ।
• दोनों लूप के अंत में परिणाम के रूप में काउंट लौटाएँ।

कुशल दृष्टिकोण

हम देख सकते हैं कि gcd(a,b)=b का अर्थ है a हमेशा b का गुणक है। b (1 ≤ b ≤ N) के ऐसे सभी गुणक जो N से कम हैं, एक जोड़ा बनाएंगे। एक संख्या i के लिए यदि i के गुणक floor(N/i) से कम हैं तो गिने जाएंगे।

• फंक्शन Count_pairs(int N) N लेता है और ऐसे जोड़े की संख्या लौटाता है जिनमें जोड़े (A,B) में B, gcd है और दोनों रेंज [1,N] में हैं।
• प्रारंभिक मान count = 0 लें ऐसे जोड़े की संख्या के लिए।
• अस्थायी चर temp = N और i = 1 लें।
• while (i <= N) का उपयोग करके निम्न करें:
  • प्रत्येक i के लिए गुणकों की सीमा की गणना करें: j = N / temp
  • वर्तमान i के लिए जोड़े की संख्या होगी temp * (j - i + 1)। काउंट में जोड़ें।
  • अगले B के लिए i = j + 1 सेट करें।
  • अगली पुनरावृत्ति के लिए temp = N / i सेट करें।
• व्हाइल लूप के अंत में, परिणाम के रूप में काउंट लौटाएँ।

उदाहरण (सामान्य दृष्टिकोण)

#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