30/09/2018, 18:45
Anh chị cho em hỏi về bài này
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
hóng post must be at least
Không hiểu đề cho lắm, để lên mạng search dãy Hamming coi nó thế nào r làm thử
ra không anh Bài này hack não quá
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ố
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
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
help em với anh Làm s mà chạy tới 10^18 được đây?
Code tham khảo: http://ideone.com/6DUKUv
Cái này bạn dùng Phương pháp Quy hoạch động xem sao??
Em cám ơn anh nhiều ^^
A ơi sao k xem đc ạ? E đang cần gấp
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)…
Link tèo.