समस्या
पंचकोणीय संख्याएँ P(k) = k(3k − 1) / 2 होती हैं: 1, 5, 12, 22, 35, 51, 70, ... कुछ जोड़ों का योग भी एक पंचकोणीय संख्या होता है, जैसे P(4) + P(7) = 22 + 70 = 92 = P(8)। ऐसे जोड़े j < k ≤ n गिनिए जिनके लिए P(j) + P(k) पंचकोणीय हो। एक तेज़ जाँच काम आती है: x ठीक तब पंचकोणीय है जब 24x + 1 एक पूर्ण वर्ग s² हो और s % 6 = 5 हो।
pentagonal_pair(n) लिखिए।
इनपुट
n: इस्तेमाल होने वाला सबसे बड़ा index k।
आउटपुट
ऐसे जोड़ों (j, k) की संख्या लौटाइए जिनमें 1 ≤ j < k ≤ n हो और P(j) + P(k) पंचकोणीय हो।
सीमाएँ
1 ≤ n ≤ 1000
उदाहरण
इनपुट:
n = 7
अपेक्षित आउटपुट:
expected = 1
इनपुट:
long long n = 7;
अपेक्षित आउटपुट:
long long expected = 1;
इनपुट:
long n = 7;
अपेक्षित आउटपुट:
long expected = 1;
व्याख्या
k = 7 तक के 21 जोड़ों में से सिर्फ़ P(4) + P(7) = 92 = P(8) पंचकोणीय है, इसलिए उत्तर 1 है।
इनपुट:
n = 1
अपेक्षित आउटपुट:
expected = 0
इनपुट:
long long n = 1;
अपेक्षित आउटपुट:
long long expected = 0;
इनपुट:
long n = 1;
अपेक्षित आउटपुट:
long expected = 0;
व्याख्या
j < k ≤ 1 वाला कोई जोड़ा नहीं है, इसलिए उत्तर 0 है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
P(k) = k(3k − 1) / 2।
संकेत 2
पूर्णांक वर्गमूल से जाँचिए कि 24x + 1 पूर्ण वर्ग है या नहीं, फिर मूल को modulo 6 में जाँचिए।
संकेत 3
सिर्फ़ j < k वाले जोड़े गिने जाते हैं।
अपेक्षित जटिलता
समय O(n²), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।