जोड़े की संख्या की गणना करें (ए <=एन, बी <=एन) जैसे कि जीसीडी (ए, बी) सी ++ में बी है

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

आइए उदाहरणों से समझते हैं।

इनपुट -एन=5

आउटपुट - जोड़े की संख्या की गणना करें (ए <=एन, बी <=एन) जैसे कि जीसीडी (ए, बी) बी है - 10

स्पष्टीकरण

pairs (A <= N, B <= N) such that gcd (A , B) is B are −
(1,1), (2,1),(3,1),(4,1),(5,1),(2,2),(3,3),(4,2),(4,4), (5,5). Total 10.

इनपुट -एन=50

आउटपुट - जोड़े की संख्या की गणना करें (ए <=एन, बी <=एन) जैसे कि जीसीडी (ए, बी) बी है - 207

स्पष्टीकरण

pairs (A <= N, B <= N) such that gcd (A , B) is B are :
(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 है तो दूसरा लौटाएं। यदि दोनों बराबर हैं तो दो में से कोई भी मान लौटाएं। अगर ए> बी रिटर्न (ए-बी, बी)। यदि बी बड़ा है, तो जीसीडी (बी-ए, ए) लौटाएं। अंत में हमें gcd मान मिलता है।
फ़ंक्शन count_pairs(int N) N लेता है और जोड़े की संख्या देता है जैसे कि जोड़ी (ए, बी) में, बी जीसीडी है और दोनों रेंज [1, एन] में हैं।
ऐसे युग्मों की संख्या के लिए प्रारंभिक मान को गिनती =0 के रूप में लें।
जोड़ी के प्रत्येक मान के लिए, लूप के लिए i=1 से i=N के लिए A के लिए चलाएं और लूप के लिए नेस्टेड j=1 t j=N के लिए B.
एक जोड़ी (i,j) बनाएं और GCD(i,j) को पास करें। यदि परिणाम j के बराबर है। वेतन वृद्धि की संख्या।
दोनों लूपों के अंत में परिणाम के रूप में वापसी की गिनती होती है।

कुशल तरीका

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

फ़ंक्शन count_pairs(int N) N लेता है और जोड़े की संख्या देता है जैसे कि जोड़ी (ए, बी) में, बी जीसीडी है और दोनों रेंज [1, एन] में हैं।
ऐसे युग्मों की संख्या के लिए प्रारंभिक मान को गिनती =0 के रूप में लें।
अस्थायी चर temp=N और i=1 लें।
उपयोग करते समय (i<=N) निम्न कार्य करें
प्रत्येक के लिए मैं गुणकों की सीमा की गणना करता हूं जैसे j=N/temp
धारा i के लिए युग्मों की संख्या अस्थायी होगी*(i-j+1)। गिनती में जोड़ें।
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