सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

बहुत अधिक भाजकों वाली त्रिकोणीय संख्या

वह पहली त्रिकोणीय संख्या खोजिए जिसके कम से कम d भाजक हों।

आप क्या सीखेंगे

  • अभाज्य गुणनखंडन से भाजकों की संख्या निकालना
  • त्रिकोणीय संख्याओं का सूत्र इस्तेमाल करना
  • सह-अभाज्य गुणनखंडों के गुणनफल को अलग-अलग करना

समस्या

त्रिकोणीय संख्याएँ उस त्रिभुज के बिंदु गिनती हैं जिसकी पंक्तियों में 1, 2, 3, ... बिंदु हों: T(1) = 1, T(2) = 3, T(3) = 6, और T(k) = k(k + 1) / 2। इन्हें क्रम से देखते जाइए और उस पहली संख्या पर रुकिए जिसके कम से कम d धनात्मक भाजक हों (1 और खुद संख्या भी गिने जाते हैं)।

highly_divisible_triangular(d) लिखिए।

बड़े मामलों में भाजकों को एक-एक करके गिनना बहुत धीमा है। इसके बजाय संख्या का अभाज्य गुणनखंडन कीजिए: अगर n = p^a × q^b × ... हो, तो उसके (a + 1)(b + 1)... भाजक होते हैं। चूँकि k और k + 1 में कोई साझा गुणनखंड नहीं होता, आप दोनों का गुणनखंडन अलग-अलग कर सकते हैं।

इनपुट

d: कम से कम कितने भाजक चाहिए।

आउटपुट

कम से कम d भाजकों वाली पहली त्रिकोणीय संख्या लौटाइए।

सीमाएँ

1 ≤ d ≤ 300

उदाहरण

उदाहरण 1
इनपुट:
d = 4

अपेक्षित आउटपुट:
expected = 6
इनपुट:
long long d = 4;

अपेक्षित आउटपुट:
long long expected = 6;
इनपुट:
long d = 4;

अपेक्षित आउटपुट:
long expected = 6;

व्याख्या

1 का एक भाजक है और 3 के दो, लेकिन 6 के चार हैं (1, 2, 3, 6), इसलिए उत्तर 6 है।

उदाहरण 2
इनपुट:
d = 9

अपेक्षित आउटपुट:
expected = 36
इनपुट:
long long d = 9;

अपेक्षित आउटपुट:
long long expected = 36;
इनपुट:
long d = 9;

अपेक्षित आउटपुट:
long expected = 36;

व्याख्या

28 के छह भाजक हैं और 36 = 2² × 3² के 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), इसलिए उत्तर 36 है।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

T(k) = k(k + 1) / 2, और k व k + 1 में कोई साझा गुणनखंड नहीं होता।

संकेत 2

k और k + 1 में से जो सम हो उसे आधा कीजिए, फिर दोनों हिस्सों के भाजक अलग-अलग गिनिए।

संकेत 3

सह-अभाज्य संख्याओं के गुणनफल के भाजकों की संख्या उनकी अपनी गिनतियों का गुणनफल होती है।

अपेक्षित जटिलता

समय O(K √K), जहाँ K आज़माई गई त्रिकोणीय संख्याओं की गिनती है, अतिरिक्त स्थान O(1)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।