等价转换一下题意：

求关于 $x$ 的同余方程 $st + x \times delta \equiv ed \pmod {2^{base}}$ 的最小正整数解。

稍微转化一下：$x \times delta + y \times 2^{base} = (ed-st + 2^{base}) \bmod 2^{base} $。

根据裴蜀定理判掉无解的情况，然后跑一个 exgcd ，解出一组解，再把它放到 $[0,m)$ 内，就完事了。

复杂度 $O(Tbase)$

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,m;
void exgcd(int a,int b,int &x,int &y){
	if(b==0) x=1,y=0;
	else{
		exgcd(b,a%b,x,y);
		int z=x;
		x=y,y=z-a/b*y;
	}
}
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int base,st,ed,d;
	while(1){
		cin>>base;
		if(base==0) break;
		cin>>st>>ed>>d;
		int r=1;
		for(int i=1;i<=base;i++) r*=2;
		base=r;
		int t=(ed-st+base)%base;
		if(t%gcd(base,d)!=0){
			cout<<-1<<'\n';
			continue;
		}
		int x,y;
		// cout<<base<<' '<<st<<' '<<ed<<' '<<d<<'\n';
		exgcd(d,base,x,y);
		int g=gcd(base,d);
		// cout<<x<<' '<<y<<' '<<g<<' '<<t<<'\n';
		x=x*t/g;
		g=base/g;
		x=(x%g+g)%g;
		cout<<x<<'\n';
	}
	return 0;
}