โปรแกรมนับศูนย์นำหน้าของ LCM(1..k) ใน Python

คำอธิบายโจทย์

ให้ k หา x = LCM(1, 2, ..., k) (ค่าที่หารด้วย 1..k ลงตัว) แล้วนับ trailing zeros ของ x

ตัวอย่าง

k = 6 → x = 60 → trailing zeros = 1 (โจทย์ตัวอย่างเขียน 0 แต่ควรเป็น 1)

วิธีแก้ปัญหา

Trailing zeros = จำนวน factor 10 = min(จำนวน 2, จำนวน 5) ใน LCM
แต่ LCM มี factor 2 มากกว่า 5 เสมอ → ต้องนับแค่ factor 5
= จำนวนครั้งที่ 5^i ≤ k สำหรับ i = 1, 2, ...

โค้ด Python

class Solution:
    def solve(self, k):
        res = 0
        x = 1
        while x * 5 <= k:
            res += 1
            x *= 5
        return res

ob = Solution()
k = 6
print(ob.solve(k))

อินพุต

6

เอาต์พุต

1