CAKE - Chia bánh
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Bạn muốn chia ~n~ cái bánh cho ~m~ người, ban đầu mỗi cái bánh là một phần.
Công cụ duy nhất bạn có là một dao cắt bánh, ở mỗi thao tác cắt, bạn được chia một phần bánh thành 2 phần với tỉ lệ tùy ý.
Hãy tìm cách dùng ít thao tác cắt nhất để chia bánh thành các phần chia cho ~m~ người, mỗi phần thuộc về đúng một người và lượng bánh mỗi người được nhận là bằng nhau.
Input
- Gồm một dòng chứa 2 số nguyên dương ~n~, ~m~ ~{(n, m <= 10^{18})}~
Output
- Một số nguyên duy nhất là số thao tác cắt phải sử dụng.
Sample
Input #1
3 5
Output #1
4
Hint
Với test ví dụ ở trên, ta có cách cắt như sau:
Problem source: ziwok
Bình luận
Công thức của bài này là: Ví dụ: n bánh, m người: (m/gcd(n, m)-1)*gcd(n, m) Code C++ tại đây