题目描述

海滩上有一堆桃子，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.