4895 - 项链分赃（增强版）

你和你的1个同伙偷了一串长度为n的项链，它上面有m种颜色的珠子，我们假设项链为链状的，并且每一颗珠子都 是随机分布，现在我想知道，对于给定的n，m你在最坏情况下最少需要切多少刀 才能使得你们可以通过每人获得 一些切完之后的项链，并且满足每个人得到的每种宝石的数量刚好相同，我们假设珠子的数目一定是偶数。也就是 说对于每种情况都一定存在一种解决方案。然而这才是这个问题的真正形式。

输入一行2个整数n，m意义如上所述。

n,m<=1000000000

输出1行，表示在最坏情况下需要多少刀。