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;
}