该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

输入格式

两个整数：n 与 k。

输出格式

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

2 6

4

样例1解释

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

6 2

0

样例2解释

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

3 4

3

样例3解释

在每根香肠的1/4处切开，有三人每人得到3/4根香肠，最后一人得到三个1/4长的香肠。

数据规模与约定

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