tôi cần bạn giúp t lần cuối
tôi đang có một bài tập hơi củ chuối nếu b hiểu thì bạn gợi ý giúp tôi được không
Gợi ý bài tập cùng trực nhật
Thử suy ra bài khác đơn giản hơn xem:
Hai bạn Hùng và Cường cùng học một trường nhưng ở hai lớp khác nhau. Cứ a ngày đi học thì Hùng lại trực nhật một lần, còn Cường thì cứ b ngày đi học lại trực nhật một lần. Biết lần đầu tiên hai bạn trực nhật vào cùng một ngày. Hỏi sau ít nhất bao nhiêu ngày thì cả hai cùng trực nhật một lần?
Gợi ý
Thử cho a và b là hai số nhỏ nhỏ bất kì, vẽ hai đoạn thẳng biểu diễn chu kì trực nhật của Hùng và Cường sao cho hai đoạn thẳng đó bằng nhau, rồi xem thử có gì đặc biệt không
cũng là một ý tưởng để tui thử
!!!mình góp ý nhé!:
giải thích lại VÍ DỤ:
- chu kì của H là 5 ngày 1 lần trực nhật
chu kì cuả C là 3 ngày 1 lần trực nhật
và khi bạn nhập T là ngày đầu tiên H và C trực nhật là thứ 4 có nghĩa là chu kì của H 5 ngày tính từ thứ 4
-> lần trực nhật tiếp theo của H là thứ 3 tuần sau( không tính CN)
-> lần trực nhất tiếp theo của C là thứ 7 trong tuần và cũng (không tính ngày CN)
Cứ như thế cho đến lần trực nhật cùng nhau gần nhất - đồng ý với bác @HR16 bạn nên vẽ đường biểu diễn và bạn chỉ cần lấy hai ví dụ thì bạn sẽ thấy mỗi quan hệ giữa khoảng cách ngày tn đầu tiên và ngày trực nhật gần nhất với chu kì trực nhật của Hùng và Cường
Cách này đúng, nhưng chạy rất lâu nếu a và b là số lớn, số nguyên tố, dân tình thường gọi cách này là chạy trâu . Nếu giải được cái bài mình gợi ý trên thì sẽ được một cách khác tối ưu hơn nhiều.
Lời giải
Lần trực nhật đầu tiên của Hùng cách lần trực nhật đầu tiên a ngày, lần thứ 2 là 2a ngày, lần thứ n là na ngày.
=> Kết quả phải là bội số của a (1)
Lần trực nhật đầu tiên của Cường cách lần trực nhật đầu tiên b ngày, lần thứ 2 là 2b ngày, lần thứ m là mb ngày.
=> Kết quả phải là bội số của b (2)
Cả hai bạn cùng trực lần đầu vào một ngày (3)
Từ (1), (2) và (3) => Kết quả chính là bội chung nhỏ nhất của a và b.
Cái khó nhất giờ là quy đổi ra k mà không dùng vòng lặp