切香肠(Cut Sausages)

题目描述

有 n 条香肠，每条香肠的长度相等。我们打算将这些香肠切开后分给 k 名客人，且要求每名客人获得一样多的香肠，且要将所有的香肠分配完，不做保留。

请问最少需要切几刀才能完成？一刀只能切断一条香肠，每一个客人都可以接受多段香肠。

输入格式

两个整数：n 与 k。

输出格式

单个整数：表示最少需要切几刀。

数据范围

• 对于 40% 的数据，1 ≤ n,k ≤ 50；
• 对于 70% 的数据，1 ≤ n,k ≤ 5000；
• 对于 100% 的数据，1 ≤ n,k ≤ 5,000,000。
• 对于附加数据，1 ≤ n,k ≤ 10¹⁵。

样例输入 #1

2 6

样例输出 #1

4

说明：两根香肠六人分，每根香肠切成3段，共4刀

样例输入 #2

6 2

样例输出 #2

0

说明：六根香肠两人分，不需要切

样例输入 #3

3 4

样例输出 #3

3

说明：在每根香肠的1/4处切开...

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

测试点分布