C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 312K, 提交时间: 2022-09-26 17:18:56

#include <bits/stdc++.h>

using i64 = long long;

i64 exgcd(i64 a, i64 m, i64& x, i64& y) {
    if(m == 0) {
        x = 1; y = 0;
        return a;
    } else {
        i64 x1;
        i64 d = exgcd(m, a % m, x1, x);
        y = x1 - a / m * x;
        return d;
    }
}

int main() {
    i64 A, B, C, k;
    while (scanf("%lld %lld %lld %lld", &A, &B, &C, &k) != EOF && A + B + C + k != 0) {
        i64 a = C, c = B - A, m = (1LL << k);
        i64 x, y;
        i64 g = exgcd(a, m, x, y);
        if (c % g != 0) {
            printf("FOREVER\n");
        } else {
            printf("%lld\n", ((c / g * x) % (m / g) + m / g) % (m / g));
        }
    }

    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 280K, 提交时间: 2022-11-28 17:51:33

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	ll d=exgcd(b,a%b,x,y);
	ll t=x;
	x=y;
	y=t-x*(a/b);
	return d;
}
int main(){
	ll A,B,C,k;
	while(~scanf("%lld%lld%lld%lld",&A,&B,&C,&k)){
		if (!A && !B && !C && !k) break;
		ll a=C;
		ll b=1ll<<k,c=B-A,x,y;
		ll d=exgcd(a,b,x,y);
		if(c%d!=0)
			puts("FOREVER");
		else{
			x=x*c/d;
			b=b/d;
			x=(x%b+b)%b;
			printf("%lld\n",x);
		}
	}
	return 0;	
}