Xác định số thứ tự của 1 số (tới 10^18) trong dãy số Hamming

[longhuy_32 (Nguyễn Cát Long Huy)]

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 :))

[masterq1997 (Tok1omonster)]

hóng post must be at least

[Bphvcg]

Không hiểu đề cho lắm, để lên mạng search dãy Hamming coi nó thế nào r làm thử

[longhuy_32 (Nguyễn Cát Long Huy)]

ra không anh Bài này hack não quá

[Gio (Gió)]

Số hamming sẽ có dạng n= 2^a3^b5^c
Trong đo n<10^18 a<=[log2(10^18)] ; b<=[log3(10^18)], c<=[log5(10^18)]
for 3 vòng a,b,c với cận trên thì sinh dc tất cả các số

[longhuy_32 (Nguyễn Cát Long Huy)]

a<=[log2(10^18)] ; b<=[log3(10^18)], c<=[log5(10^18)]

cái chỗ này em chưa hiểu lắm anh? Cái khúc trên số hamming kia em cũng làm phân tích ra thừa số nguyên tố, nhưng tới lúc duyệt ở vị trí thứ mấy thì bí tới 10^18 luôn

[longhuy_32 (Nguyễn Cát Long Huy)]

còn cách nào không anh? 10^18 đảm bảo chắc chắn không duyệt được, chắc phải có công thức gì đó nhưng khó quá, em ngồi nhìn mà chả biết công thức

[longhuy_32 (Nguyễn Cát Long Huy)]

help em với anh Làm s mà chạy tới 10^18 được đây?

[Gio (Gió)]

Code tham khảo: http://ideone.com/6DUKUv

[sample (<script>alert("hacked")</script>)]

Cái này bạn dùng Phương pháp Quy hoạch động xem sao??

[longhuy_32 (Nguyễn Cát Long Huy)]

Em cám ơn anh nhiều ^^

[Nguyen_Thanh_Huyen (Nguyễn Thanh Huyền)]

A ơi sao k xem đc ạ? E đang cần gấp

[rogp10]

Cái này tên chuẩn là 5-smooth number đúng hay sai thì dễ rồi. Mà chắc phải precomp quá chứ 10^18 sao chạy nổi.

Các tuplet khởi đầu: (1, 0, 0) (0, 1, 0) (2, 0, 0) (0, 0, 1) (3, 0, 0) (0, 2, 0) (1, 0, 1) (2, 1, 0) (0, 1, 1) (4, 0, 0) (2, 2, 0) (2, 0, 1)…

Code tham khảo: http://ideone.com/6DUKUv

Link tèo.