1樓：riteme
雖然這個問題在知乎上是兩三年前提出的，我還是想給乙個簡單並且不是很慢的方法。
首先，Wikipedia 上提到了下面這個遞推式：
不過 Wikipedia 貌似沒有給出由來，我寫了一篇文章解釋了為什麼上面這個式子是正確的：計算分拆數的一種方法 - riteme.site
上面的式子可以直接遞推，算出 的時間複雜度是 （整數運算視為常數時間）。由於它是乙個卷積的形式，因此可以使用 FFT 演算法來加速計算，至少可以達到 的時間複雜度。本人能力有限，按這種方法能不能更快也不是非常清楚。
2樓：Yu Deng
手打求贊。
bonus：
以下省略***位)
以上引自New partition function record: p(10^20) computed
3樓：
看組合數學方向的書吧，一般生成函式那有講。
推薦一本教材，科大的《組合數學引論》。裡面有單獨一節講正整數的分拆問題，包括有序分拆和無序分拆，分拆的ferrers圖，分拆數的生成函式。
4樓：zero
我們來考慮這麼乙個級數
猜猜看這兒是什麼？
猜對有獎哦
才怪猜出來了麼？
再想想呢？
In fact，
why?
well, it is really easy to see it since the coefficient of is just the number of the ways that you pick one from each and make a product to get
so only depends on the ways you break n into smaller numbers, which is exactly the definition of
所以……就這麼求……你把上面那個無窮乘積化成冪級數，然後you get everything
what? Convergence?
Who cares！
反正Euler大神肯定是不care的，care的同學可以好好check一下，這是乙個很好的微積分練習題，嗯
如何證明乙個數的數根 digital root 就是它對9的餘數？
QDelta 這是比較明顯的 首先有乙個性質就是10的冪模9一定與1同餘再將十進位制正整數寫成各數字與10的冪之積之和，就可以發現數與其各位數之和是模9同餘的 那不斷地操作下去直到得到一位正整數，這個數又與原數模9同餘，可不就是它在 1,9 中同餘的數。建議題主可以考慮下如果9換成11這題可以怎麼出...
1 100，挑4個數，總和為100，後乙個數是前乙個的倍數，組合有多少種？
何冬州楊巔楊豔華典生 設這四個數分別為 a,ab,abc,abcd,其中a,b,c,d為正整數，且sum a,ab,abc,abcd 100 易知a sum a,ab,abc,abcd 且4a sum a,ab,abc,abcd 即 a 100且a 100 4，故a的可能取值為1,2,4,5,10,...
Mathematica 怎麼判斷乙個數能否由兩個兩位數相乘得到？
cvgmt MemberQ Flatten Table i j, ProductOfTwoDigitNumberQ num Integer Block TwoDigitDivisors Divisors num IntersectingQ num TwoDigitDivisors TwoDigitD...