思路

  • 暴力递归
    从1计算到Integer.MAX_VALUE
  • 高等数学分析
    再来看看数学上的表达：模拟这个过程，可以写出n个方程

    y表示苹果数，由于令y最小化，可以用lagrange乘数法写出目标函数；
    另一种观点是y表征在x的向量空间中，有
    并且
    所以可以考虑从特征空间上的角度求解；
  • 数论分析
    上面给出了第i个方程；结合n方程看看，发现每一次都是n的倍数+1；
    最后一项是
    然后一顿推，不知道怎么推QAQ
    最终：y=n^n-n+1
    看到答案我就会推了，a^n-1=（a-1)(a^(n-1) +a^(n-2) + ...a+1)
    y-1=n(n^(n-1)-1) 看看是不是很像QAQ

代码

import java.util.*;
public class Apples {
    public boolean getInitial(int n,int k,int x){
        if(k==0){return true;}
        if((x-1)%n!=0){
            return false;
        }
        return getInitial(n,k-1,(x-1)*(n-1)/n);
    }
    public int getInitial(int n) {
        for(int i=1;i<=Integer.MAX_VALUE;i++){
            if(getInitial(n,n,i)){
                return i;
            }
        }
        return 0;
    }
}