問題の定式化

C 言語様の_for_ループ構造において、制御変数が k ビットの符号なし整数型として振る舞う場合の実行回数を求める問題について解説します。具体的なループ構造は以下のように定義されます。

for (variable = A; variable != B; variable += C)
    statement;

このループは、変数 variable を初期値 A で開始し、B に一致するまでステートメントを実行し、毎回 C ずつ増分します。算术演算は $2^k$ を法とするmodulo演算として扱われます。つまり、値の範囲は $0 \le x < 2^k$ であり、オーバーフロー時は $2^k$ で折り返します。

数学モデルへの変換

ループが x 回実行された後の変数の値は、初期値 A に増分 C を x 回加えたものとなります。これが終了条件 B に一致するためには、以下の合同式が成立する必要があります。

$$ A + C \cdot x \equiv B \pmod{2^k} $$

これを変形すると、以下の線形ディオファントス方程式の形式に帰着します。

$$ C \cdot x + 2^k \cdot y = B - A $$

ここで、$y$ は任意の整数です。この方程式が整数解 x を持つかどうか、また持つ場合に最小の非負整数解はいくつかが求めるべき答えとなります。

拡張ユークリッド互除法の適用

方程式 $ax + by = c$ が整数解を持つための必要十分条件は、$c$ が $\gcd(a, b)$ で割り切れることです。本問題では $a = C$、$b = 2^k$、$c = B - A$ となります。

拡張ユークリッド互除法を用いることで、$ax + by = \gcd(a, b)$ を満たす係数 $(x, y)$ を求めることができます。得られた解を元に、目的の方程式に対する解へスケール調整を行い、さらに modulo $2^k / \gcd(C, 2^k)$ における最小非負解を計算します。

もし $B - A$ が $\gcd(C, 2^k)$ で割り切れない場合、ループは終了条件に達せず無限に実行されるため、FOREVER と判定します。

実装の詳細

以下の C++ 実装では、64 ビット整数型を用いて計算を行います。$2^k$ はビットシフト演算で求めます。負の値に対する modulo 演算は言語仕様により処理が異なる可能性があるため、正の剰余を得るように調整を行っています。

#include <iostream>
#include <cstdint>

using int64 = std::int64_t;

// 拡張ユークリッド互除法
// ax + by = gcd(a, b) となる x, y を求め、gcd(a, b) を返す
int64 extended_gcd(int64 a, int64 b, int64 &x, int64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int64 x1, y1;
    int64 d = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

void solve() {
    int64 start_val, target_val, step_size, bit_width;
    while (std::cin >> start_val >> target_val >> step_size >> bit_width) {
        if (start_val == 0 && target_val == 0 && step_size == 0 && bit_width == 0) {
            break;
        }

        int64 modulus = 1LL << bit_width;
        int64 rhs = target_val - start_val;
        
        // 方程式：step_size * x ≡ rhs (mod modulus)
        // step_size * x + modulus * y = rhs
        
        int64 x, y;
        int64 gcd_val = extended_gcd(step_size, modulus, x, y);

        if (rhs % gcd_val != 0) {
            std::cout << "FOREVER" << std::endl;
        } else {
            // 解のスケール調整
            int64 mod_reduced = modulus / gcd_val;
            int64 solution = (x * (rhs / gcd_val)) % mod_reduced;
            
            // 最小非負整数解への調整
            if (solution < 0) {
                solution += mod_reduced;
            }
            std::cout << solution << std::endl;
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}