समस्या
कोई संख्या प्रचुर (abundant) तब होती है जब उसके उचित भाजकों (खुद को छोड़कर सभी भाजकों) का योग उससे ज़्यादा हो। 12 सबसे छोटी प्रचुर संख्या है: 1 + 2 + 3 + 4 + 6 = 16। कुछ संख्याएँ दो प्रचुर संख्याओं के योग के रूप में लिखी जा सकती हैं (एक ही संख्या दो बार भी ली जा सकती है, जैसे 24 = 12 + 12) और कुछ नहीं। 1 से limit तक के वे सभी धनात्मक पूर्णांक जोड़िए जो इस तरह नहीं लिखे जा सकते।
non_abundant_sums(limit) लिखिए।
sieve से सभी संख्याओं के भाजक-योग एक साथ निकालिए, प्रचुर संख्याओं की सूची बनाइए, फिर हर उस जोड़े के योग पर निशान लगाइए जो सीमा के भीतर रहता है।
इनपुट
limit: जाँची जाने वाली सबसे बड़ी संख्या।
आउटपुट
1 ≤ n ≤ limit वाले उन सभी n का योग लौटाइए जो दो प्रचुर संख्याओं का योग नहीं हैं।
सीमाएँ
1 ≤ limit ≤ 10,000
उदाहरण
इनपुट:
limit = 23
अपेक्षित आउटपुट:
expected = 276
इनपुट:
long long limit = 23;
अपेक्षित आउटपुट:
long long expected = 276;
इनपुट:
long limit = 23;
अपेक्षित आउटपुट:
long expected = 276;
व्याख्या
कोई भी दो प्रचुर संख्याएँ मिलकर 23 या उससे छोटी संख्या नहीं बनातीं, इसलिए हर संख्या गिनी जाती है: 1 + 2 + ... + 23 = 276।
इनपुट:
limit = 30
अपेक्षित आउटपुट:
expected = 411
इनपुट:
long long limit = 30;
अपेक्षित आउटपुट:
long long expected = 411;
इनपुट:
long limit = 30;
अपेक्षित आउटपुट:
long expected = 411;
व्याख्या
24 = 12 + 12 और 30 = 12 + 18 छूट जाते हैं, इसलिए उत्तर 465 − 24 − 30 = 411 है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर i के लिए 2i, 3i, 4i, ... के भाजक-योग में i जोड़िए।
संकेत 2
प्रचुर संख्याओं को बढ़ते क्रम में इकट्ठा कीजिए।
संकेत 3
हर जोड़े a ≤ b के लिए, जैसे ही a + b सीमा पार करे, भीतरी loop रोक दीजिए।
अपेक्षित जटिलता
समय O(limit log limit + A²), जहाँ A प्रचुर संख्याओं की गिनती है, अतिरिक्त स्थान O(limit)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।