โจทย์
ให้นำ a และ b ทุกค่าตั้งแต่ lo ถึง hi มาคำนวณ a^b บางค่าจะซ้ำกัน เช่น 2^4 = 4^2 = 16 ให้นับว่ามีค่าที่แตกต่างกันกี่ค่า ค่าเหล่านี้ใหญ่มาก แต่ไม่จำเป็นต้องคำนวณออกมาเลย ให้เขียน a ในรูป r^k โดยที่ r ไม่ได้เป็นจำนวนยกกำลังสมบูรณ์ (perfect power) แล้วจะได้ a^b = r^(k × b) จำนวนยกกำลังสองจำนวนจะเท่ากันก็ต่อเมื่อมี r ตัวเดียวกันและเลขชี้กำลัง k × b เท่ากัน
จงเขียนฟังก์ชัน distinct_powers(lo, hi)
อินพุต
lo: ฐานและเลขชี้กำลังที่น้อยที่สุด
hi: ฐานและเลขชี้กำลังที่มากที่สุด
เอาต์พุต
คืนค่าจำนวนค่าที่แตกต่างกันของ a^b โดยที่ lo ≤ a ≤ hi และ lo ≤ b ≤ hi
เงื่อนไข
2 ≤ lo ≤ hi ≤ 100
ตัวอย่าง
อินพุต:
lo = 2
hi = 4
ผลลัพธ์ที่คาดหวัง:
expected = 8
อินพุต:
long long lo = 2;
long long hi = 4;
ผลลัพธ์ที่คาดหวัง:
long long expected = 8;
อินพุต:
long lo = 2;
long hi = 4;
ผลลัพธ์ที่คาดหวัง:
long expected = 8;
คำอธิบาย
ค่าทั้งเก้าคือ 4, 8, 16, 9, 27, 81, 16, 64, 256 โดย 16 ปรากฏสองครั้ง จึงมีค่าที่แตกต่างกัน 8 ค่า
อินพุต:
lo = 7
hi = 7
ผลลัพธ์ที่คาดหวัง:
expected = 1
อินพุต:
long long lo = 7;
long long hi = 7;
ผลลัพธ์ที่คาดหวัง:
long long expected = 1;
อินพุต:
long lo = 7;
long hi = 7;
ผลลัพธ์ที่คาดหวัง:
long expected = 1;
คำอธิบาย
มีเพียง 7^7 คำตอบจึงเป็น 1
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
หา r ที่เล็กที่สุดและ k ที่ใหญ่ที่สุดซึ่ง r^k = a
คำใบ้ 2
a^b เท่ากับ r^(k × b) ดังนั้นคู่ (r, k × b) ใช้ระบุค่านั้นได้
คำใบ้ 3
ใส่คู่เหล่านี้ลงในเซตแล้วนับจำนวน
ความซับซ้อนที่คาดหวัง
เวลา O((hi − lo)² log hi), หน่วยความจำเพิ่ม O((hi − lo)²)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน