zstu.4014.水手分椰子(数学推导)

时间:2024-01-09 20:24:38

深入浅出学算法015-水手分椰子

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 1827  Solved: 524

Description

n个水手来到一个岛上,采了一堆椰子后,因为疲劳都睡着了。一段时间后,第一个水手醒来,悄悄地将椰子等分成n份,多出一个椰子,便给了旁边的猴子,然后自己藏起一份,再将剩下的椰子重新合在一起,继续睡觉。不久,第二名水手醒来,同样将椰子了等分成n份,恰好也多出一个,也给了猴子。然而自己也藏起一份,再将剩下的椰子重新合在一起。以后每个水手都如此分了一次并都藏起一份,也恰好都把多出的一个给了猴子。第二天,n个水手醒来,发现椰子少了许多,心照不喧,便把剩下的椰子分成n份,恰好又多出一个,给了猴子。请问水手最初最少摘了多少个椰子?

Input

多组测试数据,每组输入1个整数n(1 < n < 9)

Output

对于每组测试数据输出一行,值为最初摘的椰子数

Sample Input

5

Sample Output

15621

HINT

多种可能性的情况下只求最小值。

 #include<stdio.h>
#include<math.h>
int main ()
{
// freopen ("a.txt" , "r" , stdin ) ;
int n ;
while (~ scanf ("%d" , &n) ) {
long long tmp = ;
for (int i = ; i <= n + ; i++) {
tmp *= n ;
}
printf ("%lld\n" , (long long) tmp - (n - ) ) ;
}
return ;
}

这道题目告诉我,可以先用暴力写,再找规律。orz