設f(n,m) $f(n,m)$表示剩余n $n$個石子且這次最多取m $m$時的NP $NP$狀態，顯然這個函數在m $m$上是單調的，同時狀態的轉移產生一條對角線且隨著n $n$的增大逐漸右移，故從下到上可以在O(n) $O(n)$下算出某個點的狀態。

然而這并沒什么卵用，因為這道題的n≤10 8  $n/le 10^8$。

考慮k=2 $k=2$時的情況，P $P$點集合為斐波那契數列。觀察這個規律的證明： 由Zeckendorf定理可知，任意正整數可以表示為不相鄰的斐波那契數的和且這個組合對每個數唯一。設MIN(x) $MIN(x)$表示x $x$用斐波那契數分解之后的最小的數，以下欲證f(n)=min{i|f(n,i)=P}=MIN(n) $f(n)=/min/{i|f(n,i)=P/}=MIN(n)$。 顯然f(2)=1=MIN(2) $f(2)=1=MIN(2)$，以下對n $n$進行歸納。 對于0<x<MIN(n) $0<x<MIN(n)$，注意到MIN(n?x)=MIN(MIN(n)?x) $MIN(n-x)=MIN(MIN(n)-x)$。 (1)因為MIN(MIN(n)?x)≤2x $MIN(MIN(n)-x)/le 2x$，故0<x<MIN(n) $0<x<MIN(n)$的轉移一定達到N $N$點。 (2)因為MIN(n-MIN(n))>2MIN(n)MIN(n?MIN(n))>2MIN(n) $MIN(n-MIN(n))>2MIN(n)$，故此時轉移到了PP $P$點。 其中(1)的證明很模糊，將會為k/ge 2k≥2 $k/ge 2$的情況進行詳細的證明，故略去。

從k=2k=2 $k=2$的證明想到，為任意的kk $k$構造一個數列AA $A$，使其可以同樣地唯一表示[1,n][1,n] $[1,n]$的數同時相鄰數比大于k $k$。構造很簡單： 設X i  $X_i$表示A i  $A_i$可以分解[1,X i ] $[1,X_i]$的數，那么A i+1 =X i +1 $A_{i+1}=X_i+1$，X i+1 =X i +1+X j |max{j|A i+1 A j  >k} $X_{i+1}=X_i+1+X_j|max/{j|/frac {A_{i+1}} {A_j} > k/}$。 X i+1 X i+1 A i+2 ?1A i+2 A i  =X i +X j +1=A i+1 +X j =A i+1 +A j+1 ?1=A i+1 +A j+1 =A i?1 +A j |min{j|A i?1 A j  ≤k}   $$/begin{align}X_{i+1}&=X_i+X_j+1//X_{i+1}&=A_{i+1}+X_j//A_{i+2}-1&=A_{i+1}+A_{j+1}-1//A_{i+2}&=A_{i+1}+A_{j+1}//A_i&=A_{i-1}+A_j|min/{j|/frac {A_{i-1}} {A_j}/le k/}///end{align}$$ 以下證明對于任意A i =a+b $A_i=a+b$，MIN(a)b ≤k $/frac {MIN(a)} b /le k$。 設A j i   $A_{j_i}$表示對于A i ?1 $A_i-1$的從小到大第i $i$個分解。 從b=1 $b=1$開始推導，此時b $b$與MIN(A i ?b) $MIN(A_i-b)$都會落在[1,k] $[1,k]$上，故成立。 此后產生A j 1   $A_{j_1}$次減1，期間顯然成立。 當b=A j 1  +1 $b=A_{j_1}+1$時，a $a$在之前的MIN $MIN$被完全消去，也就是說，此時的MIN(a) $MIN(a)$變為A j 2   $A_{j_2}$，同時，由于j 1 =max{j|A j 2  A j  >k} $j_1=max/{j|/frac {A_{j_2}} {A_j} > k/}$，故此時kb≥A j 2  =MIN(a) $kb/ge A_{j_2}=MIN(a)$。 而之后在A j 2   $A_{j_2}$被完全消去之前，都保持滿足kb≥MIN(a) $kb/ge MIN(a)$，因為這期間產生的所有MIN $MIN$都小于A j 2   $A_{j_2}$。 在A j 2   $A_{j_2}$被完全消去時，推導同對A j 1   $A_{j_1}$的推導，即當A j i   $A_{j_i}$被消去時，b=A j i  +1 $b=A_{j_i}+1$。

故對于k>2 $k>2$，可以采用與k=2 $k=2$時的證明相同的方法證明f(n)=MIN(n) $f(n)=MIN(n)$。 那么生成了A $A$之后就可以貪心分解n $n$，即可得出結果。 生成A $A$所需的復雜度為O(|A|) $O(|A|)$： A i A i?1   =A i?1 A i?1  +A j A i?1  =1+A j A i?1  ≥1+1k    $$/begin{align}/frac {A_i} {A_{i-1}}&=/frac {A_{i-1}} {A_{i-1}} + /frac {A_j} {A_{i-1}}//&=1+/frac {A_j} {A_{i-1}}//&/ge 1+ /frac 1 k/end{align}$$ 故總的復雜度為O(log 1+1k  n) $O(log_{1+/frac 1 k}n)$。