โจทย์
คืนค่าตัวคูณร่วมน้อยที่สุดของ a และ b ซึ่งเป็นค่าบวกที่น้อยที่สุดที่ทั้งสองจำนวนหารลงตัว lcm(a, b) = a / gcd(a, b) × b
ให้เขียนฟังก์ชัน lcm(a, b)
อินพุต
a: จำนวนบวกตัวแรก b: จำนวนบวกตัวที่สอง
เอาต์พุต
คืนค่า lcm(a, b)
เงื่อนไข
1 ≤ a, b ≤ 1,000,000,000
ตัวอย่าง
ตัวอย่างที่ 1
อินพุต:
a = 4
b = 6
ผลลัพธ์ที่คาดหวัง:
expected = 12อินพุต:
long long a = 4;
long long b = 6;
ผลลัพธ์ที่คาดหวัง:
long long expected = 12;อินพุต:
long a = 4;
long b = 6;
ผลลัพธ์ที่คาดหวัง:
long expected = 12;คำอธิบาย
จำนวนที่หารด้วย 4 ลงตัว: 4, 8, 12…; จำนวนที่หารด้วย 6 ลงตัว: 6, 12…; ค่าร่วมที่น้อยที่สุดคือ 12
ตัวอย่างที่ 2
อินพุต:
a = 7
b = 7
ผลลัพธ์ที่คาดหวัง:
expected = 7อินพุต:
long long a = 7;
long long b = 7;
ผลลัพธ์ที่คาดหวัง:
long long expected = 7;อินพุต:
long a = 7;
long b = 7;
ผลลัพธ์ที่คาดหวัง:
long expected = 7;คำอธิบาย
ตัวเลขใด ๆ เมื่อนำมาหาค่า LCM กับตัวเองจะได้ตัวเลขนั้นเอง เช่น 7
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ใช้ความสัมพันธ์ระหว่าง gcd กับ lcm แทนการไล่หา multiple
คำใบ้ 2
คำนวณ gcd ก่อน แล้วค่อยรวมสองจำนวนอย่างระวัง
คำใบ้ 3
หารก่อนคูณเพื่อลดความเสี่ยง overflow แม้ input จะใหญ่
ความซับซ้อนที่คาดหวัง
เวลา O(log min(a, b)), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน