POJ 2115 循環次數：同餘方程 + 64 位整數處理 2^k 模數

問題轉化

for 循環：i = x; i != y; i = (i + m) mod 2^n。求最小循環次數 t 使 x + m*t ≡ y (mod 2^n)。
即 m*t ≡ y-x (mod 2^n)，同餘方程求最小非負解 t。

關鍵陷阱：2^n 溢出

n ≤ 32，2^32 超出 32 位有符號整數。必須用 long long 並寫作 1LL << n，不能寫 1 << n（會先按 int 計算溢出再轉 long long）。

代碼實現

long long exgcd(long long a, long long b, long long &x, long long &y) {
    if(b==0) { x=1; y=0; return a; }
    long long d = exgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

int main() {
    long long x,y,m,n;
    while(cin>>x>>y>>m>>n) {
        if(!x&&!y&&!m&&!n) break;
        long long a=m, b=1LL<<n, c=y-x;
        long long d = gcd(a,b);
        if(c % d) { cout << "FOREVER" << endl; continue; }
        long long p,q; exgcd(a,b,p,q);
        long long mod = b/d;
        long long ans = (p * (c/d) % mod + mod) % mod;
        cout << ans << endl;
    }
}

輸出規範

無解輸出 "FOREVER"（題目要求），有解輸出最小非負 t。