算数パズルしようや

**風吹けば名無し** · 2023/09/21(木) 17:20:45.28

ある整数Nが与えられます。
「Nを、Nの各桁和か各桁積に置き換える」操作をちょうど100兆回行ったあと、N=1にできるか判定してください。

各桁和: 217→2+1+7=10
各桁積: 217→2×1×7=14

これ解けるんか？

**風吹けば名無し** · 2023/09/21(木) 17:42:40.73

>>34
そうやな
ただ多倍長整数が絡むから実計算速度は遥かに遅そうや

**風吹けば名無し** · 2023/09/21(木) 17:45:47.77

たくさん操作した時にN=1にできるか？
という表を下からのDPで前計算しておけば、各桁和のときはO(1)で判定可能
あとは愚直に各桁積を取り続ければいい