蓝桥杯算法训练VIP-猴子分苹果

题目

题目链接

题解

暴力或者数学。

先讲一下数学做法（大部分人是想不到数学做法的，因此数学做法作为补充，而压轴的暴力做法才是大部分人容易理解，容易想到的）：

现在假设猴子至少采了 x 0 {x}_{0} x0​个苹果，则第一只猴子操作后，剩余的苹果有 x 1 = x 0 − m n × ( n − 1 ) {x}_{1}=\frac{x_0-m}{n}×(n-1) x1​=nx0​−m​×(n−1)；

类似地，第2只猴子操作后，还剩苹果 x 2 = x 1 − m n × ( n − 1 ) {x}_{2}=\frac{x_1-m}{n}×(n-1) x2​=nx1​−m​×(n−1)；

……

一直这样下去，直到第 n n n只猴子操作后，还剩苹果 x n = x n − 1 − m n × ( n − 1 ) {x}_{n}=\frac{x_{n-1}-m}{n}×(n-1) xn​=nxn−1​−m​×(n−1)；

第二天，最后剩下的苹果满足 x n − m n = k \frac{x_n - m}{n} = k nxn​−m​=k（k为某一正数），即表明整除。

于是，倒推回去，可得 所以得

x 0 = n n + 1 ( n − 1 ) n ( k + m ) + ( 1 − n ) m x_0 = \frac{n^{n+1}}{(n-1)^n} (k + m) + (1 - n) m x0​=(n−1)nnn+1​(k+m)+(1−n)m

题目要求 x 0 x_0 x0​“至少”是多少，为保证 x 0 x_0 x0​为整数，则要使 ( k + m ) = = ( n − 1 ) n (k + m) == (n - 1)^n (k+m)==(n−1)n，于是得

x 0 = n n + 1 + ( 1 − n ) m x_0 = n^{n+1} + (1-n)m x0​=nn+1+(1−n)m

注意开long long，用pow函数算得的结果都是浮点类型的，为保证输出不是科学计数法形式，需要强转成long long后再进行输出。当然，你也可以手写for循环换实现乘方，这样就可以避免出现输出为科学计数法形式的错误。

暴力做法（这才是我推荐大家学习的做法）：

整体思路： 暴力枚举举办宴会时每只猴子能分到的桃子数，我们去判断在这种情况下是否能倒推回最开始采到桃子数，若能则先枚举到的对应的最开始的桃子数就是答案，否则继续暴力枚举。

那怎么才算是能枚举到最开始的桃子数呢？ 存在如下的递推公式： 与数学方法中的 x i x_i xi​含义一致， r e s t i rest_i resti​也表示第 i i i只猴子要进行分配的桃子数，接下来我们用 r e s t i rest_i resti​表示（因为我代码中是用的 r e s t i rest_i resti​，这样方便理解代码）。 r e s t i = m + n × r e s t i + 1 n − 1 rest_i=m+\frac{n×rest_{i+1}}{n-1} resti​=m+n−1n×resti+1​​ 我们要进行 n n n次循环，每次循环都算出前一只猴子分配的桃子数，倒推至最初采集到的桃子数。 很明显每次的 r e s t i rest_i resti​必须是个整数，这就是我们判断是否可以继续向前推进的条件，也是判断我们枚举的宴会上每只猴子的桃子数是否满足的条件。当 n × r e s t i + 1 n×rest_{i+1} n×resti+1​对 n − 1 {n-1} n−1取模不为0时，说明不可以继续推进了，即这是一个错误的枚举方案，我们继续枚举下一个。当每次都可以整除，成功循环完 n n n次，则找到最小的最初采集的桃子数了，即最终答案。

代码1

#include
using namespace std;
#define ll long long
ll n, m, ans;
int main(void) {
    cin >> n >> m;
    ans = pow(n, n + 1) - (n - 1) * m;
    cout