मान लीजिए हमारे पास एक मान n है, हमें उन जोड़ों (a, b) [a < b] की संख्या ढूंढनी है, जो ऐसे मौजूद हैं कि समीकरण a*x + b*y = n का कम से कम एक समाधान हो।
तो, यदि इनपुट n = 4 है, तो आउटपुट 2 होगा क्योंकि वैध जोड़े (1, 2) और (1, 3) हैं।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- divisors_gen() फ़ंक्शन परिभाषित करें। यह n लेगा
- divs := आकार n+1 की सूचियों की सूची। और प्रत्येक आंतरिक सूची 1 रख रही है
- divs[0] := केवल एक एलिमेंट 0 वाली सूची
- i के लिए range 2 से n तक, करें
- j के लिए range 1 से floor of (n / i) + 1 तक, करें
- इंडेक्स [i * j] पर सूची के अंत में i डालें
- j के लिए range 1 से floor of (n / i) + 1 तक, करें
- divs वापस करें लेकिन सभी आंतरिक सूचियों को उल्टा करें
- मुख्य मेथड से, निम्नलिखित करें:
- result := 0
- d_cache := divisors_gen(n+1)
- a के लिए range 1 से n - 1 तक, करें
- i := 1
- s := एक नया सेट
- जब a*i < n, करें
- b := n - a*i
- d_cache[b] में प्रत्येक d के लिए, करें
- यदि d > a, तो
- यदि d, s में नहीं है, तो
- result := result + 1
- यदि d, s में नहीं है, तो
- अन्यथा,
- लूप से बाहर आएं
- d को सेट s में डालें
- यदि d > a, तो
- i := i + 1
- result वापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
def divisors_gen(n): divs = [[1] for x in range(0, n + 1)] divs[0] = [0] for i in range(2, n + 1): for j in range(1, n // i + 1): divs[i * j].append(i) return [i[::-1] for i in divs] def solve(n): result = 0 d_cache = divisors_gen(n+1) for a in range(1, n): i = 1 s = set([]) while a*i < n: b = n - a*i for d in d_cache[b]: if d > a: if d not in s: result += 1 else: break s.add(d) i += 1 return result n = 4 print(solve(n))
इनपुट
4
आउटपुट
2