CAKE - Chia bánh

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
codey
Problem types
Allowed languages
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:

image.png

Problem source: ziwok

Comments

Please read the guidelines before commenting.


  • 4
    tri_88  commented on Dec. 27, 2023, 12:51 a.m.

    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