#include<iostream>
using namespace std;

long long gcd(long long,long long);
long long lcm(long long,long long);
long long m1,n1;

int main()
{
	int a,b,c,k;
	while(cin>>a>>b>>c>>k)
	{
		if(!a&&!b&&!c&&!k)
			break;
		if(a==b)
		{
			cout<<0<<endl;
			continue;
		}
		if(c==0)
		{	
			cout<<"FOREVER"<<endl;
			continue;
		}
		long long t=1;
		for(int i=0;i<k;i++)
			t<<=1;
		long long m=gcd(c,t);
		if((b-a)%m)
		{
			cout<<"FOREVER"<<endl;
			continue;
		}
		int p=(b-a)/m*m1;
		int x=t/m;
		if(x)
		{		
			if(p>0)
			{
				p-=(p/x)*x;
			}
			else if(p<0)
			{
				p+=(-p)/x*x;
				p+=x;
			}
		}
		if(p<0)
		{
			cout<<"FOREVER"<<endl;
		}
		else cout<<p<<endl;
		//cout<<t<<endl;
	}
	return 0;
}

long long gcd(long long m,long long n)
{
	if(m==0)
        {
		m1=0;
		n1=1;	
		return n;
	}
	else
	{
		long long tmp=gcd(n%m,m);
		long long p1=n1-n/m*m1;
		long long p2=m1;
		m1=p1;
		n1=p2;
		return tmp;
	}
}


long long lcm(long long a,long long b)
{
	return (a*b)/gcd(a,b);
}

• Re:欧几里德扩展算法，怎么错了？ (27) niyuzhe 2007-07-18 19:45:24
  • Re:欧几里德扩展算法，怎么错了？ (11) niyuzhe 2007-07-18 20:08:04
• Re:欧几里德扩展算法，怎么错了？ (6) niyuzhe 2007-07-18 20:43:25
• Re:欧几里德扩展算法，怎么错了？ (46) niyuzhe 2007-07-18 20:51:17