#3865. 猴子吃桃(C++三级)

猴子吃桃(C++三级)

题目描述

海滩上有一堆桃子,N只猴子来分。第一只猴子把这堆桃子平均分为N份,多了一个,这只猴子把多的一个扔入海中,拿走了一份。第二只猴子接着把剩下的桃子平均分成N份,又多了一个,它同样把多的一个扔入海中,拿走了一份。第三、第四、……,第N只猴子仍是最终剩下的桃子分成N份,扔掉多了的一个,并拿走一份。

编写程序,输入猴子的数量N,输出海滩上最少的桃子数,使得每只猴子都可吃到桃子。

输入一个整数N。输出输出当猴子数量为N时海滩上最少的桃子数。结果保证在int型范围内。

样例输入

2

样例输出

7

思路:暴力枚举+贪心

要想使最后的桃子总数最小,我们一定从a[1]开始遍历,一份为1个桃子开始遍历。遍历到的猴子必须满足他的桃子可以平均分成n-1份,如果不能平均分成n-1份,就说明当前的猴子不能把桃子平均分成n份多1个,不满足题目,重新枚举。不满足条件的继续从a[1]开始遍历,一份为2个桃子开始遍历…

Limitation

1s, 1024KiB for each test case.