Namaran

Code daily. Without assist.

2026-09-04

skip.rs

const A: u64 = 6364136223846793005;
const C: u64 = 1442695040888963407;

fn skip(state: u64, n: u64) -> u64 {
}

シードから始まる乱数生成器があり、1回進むたびに状態 s が「s * A + C を2の64乗で割った余り」に置き換わります。状態 state から n 回進めた後の状態を返す skip を書いてください。途中の状態から実行を再現するのに使うので、n が 10の12乗程度でもすぐに返る必要があります。n が 0 なら state をそのまま返します。

入力例 1

skip(0, 1)

出力例 1

1442695040888963407

入力例 2

skip(42, 0)

出力例 2

42

入力例 3

skip(42, 1_000_000_000_000)

出力例 3

1621903161643487274
Reference
fn skip(state: u64, n: u64) -> u64 {
    let (mut s, mut mul, mut add) = (state, A, C);
    for bit in 0..64 {
        if (n >> bit) & 1 == 1 {
            s = s.wrapping_mul(mul).wrapping_add(add);
        }
        add = add.wrapping_mul(mul).wrapping_add(add);
        mul = mul.wrapping_mul(mul);
    }
    s
}

1回進める操作は、状態 s を s * A + C へ移す一次関数 f です。f を2回続けると f(f(s)) = (s * A + C) * A + C = s * A * A + (C * A + C) となり、これも「掛けて足す」形をしています。そこで、掛ける数 mul と足す数 add の組で「f を何回か続けた関数」を表します。ループの後半の2行がこの組を自分自身と合成する計算で、f を 2の bit 乗回続けた関数から、2の bit + 1 乗回続けた関数を作ります。新しい add は古い mul を使うので、mul より先に更新します。

n を2進数で見て、bit 番目が 1 のときだけ、その時点の組を s に適用します。適用する関数はどれも同じ f を何回か続けたものなので、順番を入れ替えても結果は変わらず、下のビットから順に適用してかまいません。n が 10の12乗でも、ループは64回で終わります。

2の64乗で割った余りを取る計算は、u64 の wrapping_mul と wrapping_add がそのまま行ってくれます。* と + で書くと、オーバーフローの検査が有効なビルド(デバッグビルドの既定)では、あふれた時点で panic します。

掲載したのは参考実装で、唯一の正解ではありません。n 回ループして1回ずつ進める実装でも結果は同じですが、n が 10の12乗だと、返るまでに長い時間がかかります。