โจทย์ทั้งหมด
ง่าย 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

จำนวนยกกำลังที่ไม่ซ้ำกัน

นับจำนวนค่าที่แตกต่างกันของ a ยกกำลัง b เมื่อ a และ b อยู่ในช่วงที่กำหนด

สิ่งที่คุณจะได้เรียนรู้

  • ลดฐานให้เหลือรากที่เล็กที่สุด
  • เปรียบเทียบจำนวนยกกำลังขนาดมหึมาโดยไม่ต้องคำนวณ
  • นับค่าที่ไม่ซ้ำกันด้วยเซต

โจทย์

ให้นำ 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

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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 ค่า

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก