問題

数直線上にうさぎがいる。 うさぎは数直線上の位置 $x$ にいるとき位置 $4x + 3$ あるいは位置 $8x + 7$ にジャンプできる。 体力の問題でうさぎは高々 $10^5$ 回のジャンプしかできない。 $\bmod 10^9 + 7$ で $0$ な位置まで移動できるか？

解法

問題となっている操作は関数 $f_2(x) = 4x + 3$ と関数 $f_3(x) = 8x + 7$ であるが、これらは $f_1(x) = 2x + 1$ を使って $f_2 = f_1^2$ および $f_3 = f_1^3$ と書ける。 $f_1$ を使って $5 \cdot 10^5$ 回ぐらい以内に $0$ まで移動できるかを確認すれば、その結果から答えは復元できる。 移動回数の上限 $L = 10^5$ と法 $M = 10^9+7$ を変数としてかつ加算や剰余は $O(1)$ だとすると、計算量は $O(\min { L, M })$ である。

メモ

  • これ好き
  • 一般の操作 ($5x + 12$ など) が足されても解けるか？
    • $1024x + 1023$ みたいな操作なら足されても解ける
    • $2x$ と $2x + 1$ みたいな関係にあれば解けそう？
    • 「イデアルとしての和が単項イデアルならばよい」みたいな雰囲気の主張ができてほしさある
    • 関数合成でなくて多項式の積だったなら可能だろうか？
  • 「高々 $10^5$ 回しかジャンプできない」の制約を落としても解けるか？
    • 離散対数問題にもなってないし難しそう
    • それでも高々 $10^9+7$ 回見ればいいので埋め込める

リンク