2070 : 库洛里多的继承者

时间限制:1 Sec 内存限制:128 MiB
提交:65 答案正确:14

提交 状态 讨论区

题目描述

库洛里多是一个伟大的魔法师,他想找一个有资质的人来继承他创造的库洛牌。
这天,库洛里多遇见了你,他想知道你是否是他要找的继承者。

库洛里多一共有n(2<=n<=100000)张库洛牌,最上面的一张牌是“无”。如果每次把最上面的m(1<=m<n)张牌移动到最下面而不改变它们的顺序及朝向,那么至少经过多少次这样的移动,“无”牌又会出现在最上面。

如果你能回答这个问题,你就能成为库洛牌的继承者。

输入

两个整数n,m(2<=n<=100000,1<=m<n)

输出

使“无”牌再次出现在最上面的最少移动次数。

样例输入

复制
54 12

样例输出

复制
9

提示

最小公倍数

来源

MOLEI