समस्या
मान लीजिए s(n) संख्या n के उचित भाजकों (ख़ुद n को छोड़कर उसके सभी भाजकों) का योग है। दो अलग-अलग संख्याएँ a और b मित्र संख्याओं का जोड़ा (amicable pair) बनाती हैं जब s(a) = b और s(b) = a हो। सबसे छोटा जोड़ा 220 और 284 है: s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 और s(284) = 1 + 2 + 4 + 71 + 142 = 220।
amicable_pair(limit) लिखिए।
limit तक की हर n के लिए s(n) एक-एक करके निकालना धीमा है। छलनी (sieve) बेहतर काम करती है: हर d के लिए, d से बड़े d के हर गुणज में d जोड़ दीजिए।
इनपुट
limit: किसी जोड़े की किसी भी संख्या का अधिकतम संभव मान।
आउटपुट
जोड़ों [a, b] की list लौटाइए, जहाँ a < b ≤ limit हो, और जोड़े a के आरोही क्रम में हों। कोई जोड़ा तभी शामिल होता है जब उसकी दोनों संख्याएँ limit से बड़ी न हों। पूर्ण संख्याएँ (जिनके लिए s(n) = n) जोड़ा नहीं मानी जातीं। कोई जोड़ा न हो तो खाली list लौटाइए।
सीमाएँ
1 ≤ limit ≤ 200,000
उदाहरण
इनपुट:
limit = 1500
अपेक्षित आउटपुट:
expected = [
[220, 284],
[1184, 1210]
]
इनपुट:
long long limit = 1500;
अपेक्षित आउटपुट:
std::vector<std::vector<long long>> expected = {
{220, 284},
{1184, 1210}
};
इनपुट:
long limit = 1500;
अपेक्षित आउटपुट:
long[][] expected = new long[][] {
new long[] {220, 284},
new long[] {1184, 1210}
};
व्याख्या
s(220) = 284 और s(284) = 220, तथा s(1184) = 1210 और s(1210) = 1184। दोनों जोड़े 1500 के अंदर आते हैं: [[220, 284], [1184, 1210]]।
इनपुट:
limit = 250
अपेक्षित आउटपुट:
expected = []
इनपुट:
long long limit = 250;
अपेक्षित आउटपुट:
std::vector<std::vector<long long>> expected = {};
इनपुट:
long limit = 250;
अपेक्षित आउटपुट:
long[][] expected = new long[][] {};
व्याख्या
220 तो 250 से बड़ा नहीं है, लेकिन उसका साथी 284 बड़ा है, इसलिए कोई जोड़ा नहीं बनता: []।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
1 से limit / 2 तक के हर d के लिए, 2d, 3d, 4d और आगे के योगों में d जोड़िए।
संकेत 2
हर a के लिए b को उसके भाजकों का योग मानिए, और जाँचिए कि b सीमा के अंदर है और b के भाजकों का योग a है।
संकेत 3
a < b की शर्त से हर जोड़ा एक ही बार आता है और पूर्ण संख्याएँ अपने-आप छूट जाती हैं।
अपेक्षित जटिलता
समय O(limit log limit), अतिरिक्त स्थान O(limit)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।