30/09/2018, 18:45

Cho em hỏi về bài dãy số Hamming tới 10^18

Chào anh chị. Anh chị cho em hỏi về bài này:
Dãy số nguyên dương tăng dần, trong đó ước nguyên tố của mỗi số không quá 5 được gọi là dãy Hamming. Như vậy, 10 = 2×5 sẽ là một số trong dãy Hamming, còn 26 = 2×13 – không thuộc dãy Hamming.
Phần đầu của dãy Hamming là 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, . . .
Yêu cầu: Cho số nguyên x(1<=x<=10^18) . Hãy xác định số thứ tự của trong dãy Hamming.
Dữ liệu: vào từ tập tin văn bản HAMMING.INP:

  • Dòng đầu tiên chứa số nguyên t– số lượng tests (1<=t<=10^5)
  • Mỗi dòng tiếp theo chứa một số nguyên
    Kết quả: ghi ra tập tin văn bản HAMMING.OUT, kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên hoặc thông báo Not in sequence.

Em làm bài này thì ok, nhưng cùng lắm em chỉ chạy tới được có 10^6, còn bài này tới 10^18 chắc phải có quy luật gì đó? Mong mọi người chỉ giáo. Em cám ơn :))

Bài liên quan
0