ChisocDust

用户名：OnC137

访问量：1323

签　名：

太阳就在眼前，何须留恋蜡烛

等　　级
排　　名	4102
经　　验	1767
参赛次数	8
文章发表	2
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法训练VIP-猴子分苹果-题解（C++代码）技巧解法
浏览：584

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

蓝桥杯算法训练VIP-猴子分苹果-题解（C++代码）技巧解法

　　作者: ChisocDust　　　　发表时间：2021-03-10 19:48:49 浏览：584　|　评论：0　

原题链接：蓝桥杯算法训练VIP-猴子分苹果

【OJ刷题之路】【C语言网

# 博客链接
**题中有LaTex数学公式，这里不支持，建议到原博查看**
[链接](https://blog.csdn.net/weixin_45625573/article/details/114632727?spm=1001.2014.3001.5501)
# 参考代码

```cpp
#include<bits/stdc++.h>

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

return 0;
}
```

# 解题思路

## 方法一
写出每次剩下的桃子表达式，设$k_1,k_2,k_3...k_n$为每次分桃子时，每一份的个数，x为一开始桃子的个数
则有：
$x=nk_1+m$
$(n-1)k_1=nk_2+m$
$(n-1)k_2=nk_3+m$
$(n-1)k_3=nk_4+m$
$...$
$(n-1)k_{n-1}=nk_n+m$
用循环或者递归的方式，求出$x$关于$k_n$的变化而变化，并且**中间涉及到的除法都没有余数，若有余数那么便说明此时$k_n$的值不符合题解**

***此方法比较好理解，但是时间复杂度非常高，所以有了方法二***

## 方法二
我们举个具体例子，`n=5,m=1`，也就是有5只猴子，每次多了1个桃子，我们根据给出的输出样例可以看出最初的桃子总数有`x=15621`个，我们倒推一下：

**第一次**多了1个，也就是$x/n$余$1$那么如果我们给`x`加上`n-1`个m
`m`，就可以整除了，设：$y=x+(n-1)*m$，那么有：$y\%n==0$

**第二次**经过第一次，因为剩下的桃子`m`等于0，也就是没有多余的桃子被吃点，我们还剩
$y-\frac{y}{n-1}$个桃子由于$y$是可以被$n$整除的，那么$y-\frac{y}{n-1}$也可以被$n$整除

**第三次，第四次，第五次**和第二次相同，那么5只猴子，加上最后一次**第二天还分了一次**，一共分了`n+1`次，也就是等式$x+(n-1)\times m=n^{n+1}$成立，那么就可以求出$x=n^{n+1}-(n-1)\times m$

~~**btw：呵呵，有位大佬发了这道题的一个题解和解题思路后，被各种copy搬运，抄来抄去以至于我都找不到原作者是谁了，但是题解本身又并没有解释得很清楚，这种不求甚解还抄来抄去当作自己博文的做法真够恶心**~~
# 注意事项
这道题因为数据范围的原因，建议变量都开成`long long`类型，并且不能够直接输出结果，比如

```cpp
cout << pow(n, n + 1) - (n - 1) * m;//错误！
```
需要先声明一个`long long`类型变量，对变量赋值再输出

```cpp
ans = pow(n, n + 1) - (n - 1) * m;
cout << ans;
```
原因是输出时由于格式的原因，比如我们输入`n=8,m=8`,最后输出的结果会是`1.34218e+08`，这是无法AC的

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

ChisocDust

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【出圈】（C++代码）（典型的约瑟夫环——链表解决）

C语言训练-计算一个整数N的阶乘（C语言代码）

蓝桥杯算法训练VIP-猴子分苹果-题解（C++代码）技巧解法

评论区

精彩推荐

c primer plus 第十二章 12.1小节

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

printf基础练习2 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

罗列完美数（C语言代码）

sizeof的大作用（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

敲七（C语言代码）

ChisocDust

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【出圈】 （C++代码）（典型的约瑟夫环——链表解决）

C语言训练-计算一个整数N的阶乘 （C语言代码）

蓝桥杯算法训练VIP-猴子分苹果-题解（C++代码）技巧解法

评论区

精彩推荐

c primer plus 第十二章 12.1小节

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

printf基础练习2 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

罗列完美数 （C语言代码）

sizeof的大作用 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

敲七 （C语言代码）

【出圈】（C++代码）（典型的约瑟夫环——链表解决）

C语言训练-计算一个整数N的阶乘（C语言代码）

　　评论区

罗列完美数（C语言代码）

sizeof的大作用（C语言代码）

敲七（C语言代码）