CSU 1425 NUDT校賽 I題 Prime Summation

這個題本來有希望在比賽裡面出了的

當時也想着用遞推 因為後面的數明顯是由前面的推過來的

但是在計算的時候 因為判重的問題

。。。很無語。我打算用一個tot[i]來存i的總種樹，tot[i]+=tot[j]//j為可以由j推到i的一系列數，但這樣是不對的，會産生大量重複計算。。。

看了下标程才發現要用二維來計算出種類總數，f[i][j]+=sum(f[i-j][k]）

表示在推i數的時候，第一個素數為j的種類數，注意j一定為素數，而且k不能大于j。。。标程裡面處理的比較簡練，就學了下他的寫法。

至于推導出式子，則可以用遞歸，比較簡練的是用遞推。

這是錯誤的代碼：是我之前沒把種類數計算好，并且推導式子用的是遞歸：

ac代碼：