โจทย์
จำนวนห้าเหลี่ยมคือ 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: ดัชนี 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;
คำอธิบาย
จาก 21 คู่ที่ k ไม่เกิน 7 มีเพียง 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 เป็นกำลังสองสมบูรณ์ด้วยรากที่สองแบบจำนวนเต็ม แล้วตรวจรากนั้นด้วยมอดุโล 6
คำใบ้ 3
นับเฉพาะคู่ที่ j < k
ความซับซ้อนที่คาดหวัง
เวลา O(n²), หน่วยความจำเพิ่ม O(n)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน