โจทย์
ร้านเบเกอรี่แห่งหนึ่งบรรจุคุกกี้ลงกล่องได้ทุกขนาดตั้งแต่ lo ถึง hi ชิ้น ร้านต้องการอบคุกกี้ในจำนวนที่แบ่งใส่กล่องขนาดใดก็ได้ในช่วงนี้จนเต็มพอดีโดยไม่มีเหลือ คำตอบคือจำนวนบวกที่น้อยที่สุดที่หารด้วยจำนวนเต็มทุกตัวตั้งแต่ lo ถึง hi ได้ลงตัว ซึ่งก็คือ ค.ร.น. (ตัวคูณร่วมน้อย) ของจำนวนเหล่านั้นนั่นเอง
จงเขียนฟังก์ชัน smallest_multiple(lo, hi)
อินพุต
lo: ขนาดกล่องที่เล็กที่สุด
hi: ขนาดกล่องที่ใหญ่ที่สุด
เอาต์พุต
คืนค่าจำนวนเต็มบวกที่น้อยที่สุดที่ lo, lo + 1, ..., hi ทุกตัวหารได้ลงตัวโดยไม่มีเศษ
เงื่อนไข
1 ≤ lo ≤ hi ≤ 40 (คำตอบเก็บในจำนวนเต็มแบบมีเครื่องหมายขนาด 64 บิตได้)
ตัวอย่าง
อินพุต:
lo = 1
hi = 6
ผลลัพธ์ที่คาดหวัง:
expected = 60
อินพุต:
long long lo = 1;
long long hi = 6;
ผลลัพธ์ที่คาดหวัง:
long long expected = 60;
อินพุต:
long lo = 1;
long hi = 6;
ผลลัพธ์ที่คาดหวัง:
long expected = 60;
คำอธิบาย
60 หารด้วย 1, 2, 3, 4, 5 และ 6 ได้ลงตัว และไม่มีจำนวนบวกที่น้อยกว่านี้ที่ทำได้ คำตอบจึงเป็น 60
อินพุต:
lo = 4
hi = 6
ผลลัพธ์ที่คาดหวัง:
expected = 60
อินพุต:
long long lo = 4;
long long hi = 6;
ผลลัพธ์ที่คาดหวัง:
long long expected = 60;
อินพุต:
long lo = 4;
long hi = 6;
ผลลัพธ์ที่คาดหวัง:
long expected = 60;
คำอธิบาย
lcm(4, 5) = 20 และ lcm(20, 6) = 60 คำตอบจึงเป็น 60 เช่นเดิม กล่องขนาดเล็กไม่ได้ทำให้คำตอบเปลี่ยนเลย
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ค.ร.น. ของทั้งช่วงสร้างได้โดยรวมทีละจำนวน
คำใบ้ 2
lcm(a, b) = a / gcd(a, b) × b
คำใบ้ 3
ให้หารก่อนคูณ ค่าระหว่างทางจะได้ไม่ใหญ่กว่าคำตอบ
ความซับซ้อนที่คาดหวัง
เวลา O(n log M), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน