Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1月前

05/17
20:46
杂题

[bzoj 4895] 项链分赃(增强版)

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

输入一行3个整数n,m意义如上所述。
n,m<=1000000000

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

1000 5

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

5

【HINT】
事实上我们发现,只要我们给队友一刀就能解决了。

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

可以发现环和链的情况是一样的,所以直接套用bzoj 4893的结论输出m 就可以了

 

[bzoj 4895] 项链分赃(增强版)