POJ 2115

和POJ 1061一样

要求最小解，就尽可能的把ax的值附到by上去，所以可以有ax=b*k+a*v（因为附到by上后必须仍上a*x的形式）。两边同除a就可得到结果。

但是，我们知道，（a,b）=1。所以k|a，也就是说，ans=(x%b+b)%b。后来加上b是为了防止负数。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

__int64 gcd(__int64 a,__int64 b){
	if(b==0) return a;
	return gcd(b,a%b);
}

void exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y){
	if(b==0){
		x=1; y=0;
		return ;
	}
	exgcd(b,a%b,x,y);
	__int64 tmp=x;
	x=y;
	y=tmp-(a/b)*y;
}

int main(){
	__int64 A,B,C,k,a,b,c;
	__int64 x,y;
	while(scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&k)&&A+B+C+k>0){
		k=1LL<<(k);
		if(A==B){
			printf("0
"); continue;
		}
		__int64 tmp;
		a=C; b=k; c=B-A;
		tmp=gcd(a,b);
		if(c%tmp!=0){
			printf("FOREVER
");
			continue;
		}
		a/=tmp; b/=tmp; c/=tmp;
		exgcd(a,b,x,y);
		x*=c;
		tmp=(x%b+b)%b;
		printf("%I64d
",tmp);
	}
	return 0;
}