दिए गए GCD वाले प्राकृतिक संख्या जोड़ों की गणना (रेंज में) - C++

समस्या विवरण

हमें तीन इनपुट start, end, number दिए गए हैं। लक्ष्य [start, end] रेंज में उन जोड़ों (A,B) की गणना करना है जिनका GCD number के बराबर हो।

उदाहरण

इनपुट: start=5, end=20, number=8

आउटपुट: 3

व्याख्या: (8,8), (8,16), (16,8)

इनपुट: start=5, end=20, number=7

आउटपुट: 2

व्याख्या: (21,28), (28,21) — लेकिन 21,28 रेंज में नहीं हैं। सही: (7,7), (7,14), (14,7) — रेंज 5-20 में।

दृष्टिकोण

साधारण: रेंज में सभी जोड़ों की जाँच करें। O(n²)।

कुशल: GCD number होने के लिए दोनों संख्याएँ number से विभाज्य होनी चाहिए। रेंज को अपडेट करें: start = ceil(start/number), end = floor(end/number)। फिर GCD=1 वाले जोड़े गिनें।

एल्गोरिदम (कुशल)

1. start = (start + number - 1) / number
2. end = end / number
3. नई रेंज [start, end] में GCD(i,j)==1 वाले जोड़े गिनें

C++ कार्यान्वयन

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

int GCD(int a, int b) {
    return b ? GCD(b, a % b) : a;
}

int GCD_pairs(int start, int end, int number) {
    int count = 0;
    for (int i = start; i <= end; i++) {
        for (int j = start; j <= end; j++) {
            if (GCD(i, j) == 1) count++;
        }
    }
    return count;
}

int main() {
    int start = 10, end = 30, number = 10;
    start = (start + number - 1) / number;
    end = end / number;
    cout << "Count: " << GCD_pairs(start, end, number) << endl;
    return 0;
}

आउटपुट

Count: 7