记录编号	592668	评测结果	A
题目名称	[POJ 2115] C Looooops	最终得分	100
用户昵称	qyd	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2024-07-28 10:08:28	内存使用	3.30 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ex_gcd(ll a,ll b,ll &x,ll &y);
ll quick_pow(int a,int n);
int main()
{
	freopen("cloops.in","r",stdin);
	freopen("cloops.out","w",stdout);
	ll A=1,B=1,C=1,K=1;
	ll x,y;
	while(A||B||C||K)
	{
		cin>>A>>B>>C>>K;
		if(!A&&!B&&!C&&!K)break;
		ll temp=K;
		K=quick_pow(2,temp);
		ll D=B-A;while(D<0)D+=K;ll ans;
		if(D%ex_gcd(C,K,x,y)!=0){cout<<"FOREVER"<<endl;continue;}
		else
		{
			ans=D/ex_gcd(C,K,x,y)*x;
			K/=ex_gcd(C,K,x,y);
			ans=(ans%K+K)%K;
			cout<<ans<<endl;
		}
	}
	return 0;	
}
ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
	if(a<b)return ex_gcd(b,a,y,x);
	if(b==0){x=1;y=0;return a;}
	else
	{
		ll xx=y+(a/b)*x;
		ll d=ex_gcd(b,a%b,xx,x);
		y=xx-(a/b)*x;
		return d;
	}
}
ll quick_pow(int a,int n)
{
	if(n==0)return 1;
	if(n==1)return a;
	ll base=quick_pow(a,n>>1);
	return base*base*(n&1?a:1);
}