本文共 1329 字，大约阅读时间需要 4 分钟。

链接：

时间限制：C/C++ 1秒，其他语言2秒

题目描述

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 
   
    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 
   
    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;}
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/82719467 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！