POJ 2115：C Looooops

Description

for (variable = A; variable != B; variable += C)

  statement;

Input

Output

Sample Input

3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0

Sample Output

0
2
32766
FOREVER

题意是问在

for (variable = A; variable != B; variable += C)

这样的情况下，循环多少次。

当中全部的数要mod 2的k次方。所以方程就是(A+C*x)%(2^k)=B，变换一下就是-C*x+(2^k)*y=A-B。解这个方程的最小正数x就可以。

又是扩展欧几里德。

代码：

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

long long yue;

void ex_gcd(long long a,long long b, long long &xx,long long &yy)
{
	if(b==0)
	{
		xx=1;
		yy=0;
		yue=a;
	}
	else
	{
		ex_gcd(b,a%b,xx,yy);

		long long t=xx;
		xx=yy;
		yy=t-(a/b)*yy;
	}
}


int main()
{
	long long A,B,C,k,k2,xx,yy;

	while(scanf_s("%lld%lld%lld%lld",&A,&B,&C,&k))
	{
		if(!A&&!B&&!C&&!k)
			break;

		k2=(1LL<<k);
		ex_gcd(-C,k2,xx,yy);

		if((A-B)%yue)
		{
			cout<<"FOREVER"<<endl;
		}
		else
		{
			xx=xx*((A-B)/yue);
			long long r=k2/yue;
			if(r<0)
				xx=(xx%r-r)%r;
			else
				xx=(xx%r+r)%r;
			printf("%lld\n",xx);
		}
	}
	return 0;
}