【Project Euler】P294: Sum of digits - experience #23のメモ（その１） - Qiita

23の倍数で各桁の和が23の数を1112まで数える 再帰関数＋lru_cache P294: Sum of digits - experience #23 は表題のように簡単そうな問題ですが、数がとんでもなく大きいのでギブアップでした。 まず普通に再帰関数で書くとこんな感じですが時間がかかって問題外。 def S(nd,m,ds): #桁 10**nd, m: 23で割った余り, ds: 桁の和 if nd == 0: return 1 if (m % 23 == 0) and ds == 23 else 0 ret = 0 for d in range(min(23-ds+1,10)): ret += S(nd-1,(m*10+d)%23,ds+d) return ret ND = 42 print((f"ND = {ND}, answer = {S(ND,0,0)})