算数パズルしようや

**風吹けば名無し** · 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:32:17.92

>>16
そうや
最初にNが与えられるから、最も都合よく操作した時にN=1にできるか判定しろって感じ

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

>>20
別に「ちょうど」は要らんかったわ
Nは単調減少することが示せるし

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

全てのNでこれが成立するのかって問いなら否
それとも成立するNをいっぱい探してみようってことなのか？

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

あーなんか解けたなこれ
事前にN<1000くらいは小さい値から全探索しておけばいいのか

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

1,10,100,1000
1,11,111,1111をつくってい感じやな

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

そんな答えでいいんか

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

これ競プロの問題とかちゃうの

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

>>23
だいたいそんな感じや
たとえば「Nが766287459のとき、操作後1にできる？」みたいな判定問題やな

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

てかこれ競技プログラミングの問題？

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

>>27
競プロやなこれ
Nを指定すればよかったわ

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

Nが123456789のとき、操作後1にできますか？
みたいな具体的な出題にすべきやったわ

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

多倍長整数を容認すれば、N<10^100くらいまでは解けそう
各桁積のときの収束速度をちゃんと確認しとらんから、限界は分からんが

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

>>29
競プロになってしまったわ
オリジナル問題

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

10^n くらいの各桁積の最大が 9^n だから (9/10)^n くらいで落ちていくんやない？

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

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

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

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