链接：https://www.nowcoder.com/acm/contest/190/E
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

Applese有个神奇的能力，TA可以把m个硬币融合成1个硬币，是不是很厉害。现在Applese有n个硬币，TA想把这个n个硬币融合成1个，请问他能完成吗?

输入描述

输入两个整数n,m(1 ≤ n, m ≤ 109)

输出描述

如果Applese能完成,输出"Yes"，否则输出"No"。

 

样例输入

10 7

样例输出

No

解题思路

首先我们可以知道当m=1时，只有n=1的时候才可以。

当m!=1时我们有两种方法可以做。

法1：融合硬币的过程就是n / m的过程，而那些不足以融合的就是n % m，而把两者加在一起一直模拟这个过程，直到n < m为止，最后判断n是否为1就行了。

代码：

#include <iostream>
using namespace std;
int main()
{
    long long n, m;
    while (cin >> n >> m)
    {
    	if (m == 1)
    	{
            if (n == 1)
                puts("Yes");
            else puts("No");
        }
        else
        {
            while (n >= m)
                n = n / m + n % m;
            if (n == 1)
                puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

法2：

我们可以假设当满足条件时共需n + a个(a为缺的)，首先我们先从a个中取1个，从n个中取m-1个，可以融合成1个。然后再从n-m+1中取m-1个，用上次融合而成的1个再次融合成1个，一直这样下去，直到最终融合成一个。我们可以发现只要n % (m - 1) == 1就可以了，这个1为一开始从a中取的。

我们也可以这样理解：首先我们先从n个中取m-1个，再借1个，就可以融合成1个，然后把借的还了。一直这样借了再还下去，直到最终融合成1个，最后这个就不用还了。所以只要借最后一个就行了，即n % (m - 1) == 1就可以了，这个1为最后借的。

提示：n % (m - 1) == 1 等于 (n - 1) % (m - 1) == 0

代码：

#include <iostream>
using namespace std;
int main()
{
    long long n, m;
    while (cin >> n >> m)
    {
    	if (m + n == 2 || m != 1 && !((n - 1) % (m - 1)))
            puts("Yes");
        else puts("No");
    }
    return 0;
}