POJ2115 C looooops 【求解线性同短方程】

POJ2115 C looooops 【求解线性同余方程】

执行了X次后

C*x+y*2^k=B-A

从A到B

本质就是求同余方程

C*x=B-A    mod    2^k

 

 

注意k的范围是32，超过int了，全用longlong

 

接下来就是求同余方程那一套了

 

a*x+b*y=gcd(a,b)这个扩展欧几里德算法解出来的x是最小的

 

还有

第一步后，方程式变为

gcd=gcd(C,2^k)

C*x/gcd+y*2^k/gcd=(B-A)/gcd

(C*x)/gcd=(B-A)/gcd    mod    2^k/gcd

 

这时候x可能得到负数，但是要在2^k/gcd范围内模成正数（道理很简单，C和2^k同时缩短gcd倍，步长和路程保持比例不变，步数是不变的），也是一个WA点。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
long long x,y;
void extend_Eulid(long long a,long long b){
    if(b == 0){
        x = 1;y = 0;
    }else{
        extend_Eulid(b,a%b);
        long long temp = x;x = y;y = temp - a/b*y;
    }
}
long long gcd(long long a,long long b)
{
	if(a<b) swap(a,b);
	return b==0?a:gcd(b,a%b);
}
long long ans;
long long  k;
bool getLinerModualSolve(long long a,long long b,long long n)
{
    long long origin_b=b;
    
	long long tmp=gcd(a,b);
	if(n%tmp!=0) return false;
	a/=tmp;b/=tmp;n/=tmp;
	extend_Eulid(a,b);
	ans=x*n;
	ans=(ans%b+b)%b;
	return true;
}
int main()
{
	#ifndef ONLINE_JUDGE
		freopen("G:/1.txt","r",stdin);
		freopen("G:/2.txt","w",stdout);
	#endif
	long long A,B,C;
	while(cin>>A>>B>>C>>k)
	{
		if(!A&&!B&&!C&&!k)
			return 0;
        long long mod=(long long)1<<k;
		if(getLinerModualSolve(C,mod,B-A))
		{
			printf("%lld\n",ans);
		}
		else
		{
			printf("FOREVER\n");
		}
	}
	return 0;
}