POJ-2115, TJU-2297, ZOJ-2305 : C Looooops
問題概要
方程式 A + B*x = C (mod 2^k)を満たす最小のxを求める問題。解がなければ指摘する。
acceptされたコード
#include <cstdio> #include <algorithm> using namespace std; typedef long long int64; int64 A, B, C, K, MOD; int64 extgcd(int64 a, int64 b, int64& x, int64& y){ int64 d = a; if(b != 0){ d = extgcd(b, a%b, y, x); y -= (a / b) * x; } else{ x = 1; y = 0; } return d; } int64 mod_inverse(int64 a, int64 mod){ int64 x, y; extgcd(a, mod, x, y); return (x % mod + mod) % mod; } bool init(){ scanf("%lld%lld%lld%lld", &A, &B, &C, &K); return K > 0; } void solve(){ MOD = 1LL<<K; int64 a = C, b = (B - A + MOD) % MOD, d = __gcd(a, MOD); if(b % d != 0){ puts("FOREVER"); } else{ a /= d; a = mod_inverse(a, MOD); b /= d; MOD /= d; printf("%lld\n", a * b % MOD); } } int main(){ for(;init();){ solve(); } return 0; }