分苹果

今天刷到一道算法题，分享一下

果园里有堆苹果，N（1＜N＜9）只熊来分。第一只熊把这堆苹果平均分为N份，多了一个，它把多的一个扔了，拿走了一份。第二只熊把剩下的苹果又平均分成N份，又多了一个，它同样把多的一个扔了，拿走了一份，第三、第四直到第N只熊都是这么做的，问果园里原来最少有多少个苹果？

可以先尝试一下再往下看，如果有好的方法欢迎加群交流！（N=5的时候，答案是3121）。

先简单分析一下这道题目，假设当第k个熊取完之后还有M个苹果，按照题目的意思，M除以N的余数恰好是1，那么第k+1只熊可以拿到(M-1)/N个苹果，第k只熊取之前有M*N/(N-1)+1个苹果。 换句话说，这堆苹果满足一个性质，对于每一只熊，取之前取之后的苹果数除以N都余1，取之后的苹果数整除(N-1)。

这样考虑的话，我们可以从最后一只熊开始向前倒推总的苹果数num，最后一只熊取走了N份苹果中的1份，所以剩下的苹果一定为N-1的倍数，所以num初始值一定为N-1的倍数。

把num初值为 N-1之后，开始倒推，上一只熊取之前的苹果数为num = num + num/(N-1)+1，再判断这个数字能否被N-1整除，若可以，继续向前倒推，若不能，说明num不满足条件，将num初值更新为2*(N - 1),重复上述过程，若nun不满足条件，再设置为3*(N-1),依次类推，直到循环中的num都能被N-1整除，这时候的num为满足条件的最小值，可能说的不是很清楚，直接看代码

def getnum(n):
    j = 1
    num = n-1
    i = 0
    while(i < n):
       if num%(n-1) != 0:
           i =0
           j += 1
           num = (n-1)*j
       else:
           i += 1
           num += 1 + num/(n-1)
    return num

再仔细分析一下这个题目，如果把每只熊取之前的苹果数记做一个序列

根据之前的分析，倒数第k次取之前的苹果数是倒数k+1次取之前的苹果扔掉一个再取走一份后剩下的，所以有关系式：

同时倒数第一只熊取之前的苹果数满足条件：

这里|表示整除，因为它需要扔掉一个然后分成N份。换种表示方式可以写成

综合到一起，所有的条件可以描述为

有没有感觉很熟悉，这不就是高中的数列递推公式？把通项公式求出来就完事了，根据上面的递推式，有

最后得到

因为xN必须是整数，所以m取值不能任意，有一定的限制，实际上已经非常明确了，要使得xN是整数，只要让m的取值恰好可以消掉中式子的分母就可以了，最终可以得到

其中

这样我们实际上求出了所有满足条件的苹果数量，如果只要最小数量，让t=1就可以啦，最终得到

这样代码就变得非常非常非常简单。

def getnum1(n):
    return n**n +1-n