समस्या
त्रिकोणीय संख्याएँ उस त्रिभुज के बिंदु गिनती हैं जिसकी पंक्तियों में 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
उदाहरण
इनपुट:
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 है।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।