POJ 2115 C Looooops 扩充欧几里得算法

POJ 2115 C Looooops 扩展欧几里得算法

链接：http://poj.org/problem?id=2115

题意：一个循环，初始值a,目标值b,中间每次加c，循环过程中数值自动对2^k取模。问多少次以后循环结束。

思路：（我会说是因为喜欢这个题的名字才些博客的吗）实际上就是一个扩展欧几里得的应用，方程式c*x+(2^k)*y=b-a.得到解以后，为了寻找最小整数解，要通过不断加/减(2^k/ans)来得到。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <ctype.h>
#include <algorithm>
#include <string>
#include <set>
#define PI acos(-1.0)
#define maxn 10005
#define INF 0x7fffffff
#define eps 1e-8
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
__int64 extend_gcd(__int64 a, __int64 b, __int64 &x, __int64 &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    __int64 r=extend_gcd(b,a%b,x,y);
    __int64 t=x;
    x=y;
    y=t-a/b*y;
    return r;
}
__int64 Pow[33];
void init()
{
    Pow[1]=2;
    for(int i=2; i<=32; i++)
    {
        Pow[i]=Pow[i-1]*2LL;
    }

}
int main()
{
    __int64 a,b,c;
    int k;
    init();
    while(scanf("%I64d%I64d%I64d%d",&a,&b,&c,&k))
    {
        if(a+b+c+k==0)
            break;
        __int64 MOD=Pow[k];
        __int64 target=(b-a+MOD)%MOD;
        __int64 x,y;
        __int64 ans=extend_gcd(MOD,c,x,y);
        if(!(target%ans))
        {
            y=(target/ans*y+MOD)%MOD;
            y=(y%(MOD/ans)+(MOD/ans))%(MOD/ans);
            printf("%I64d\n",y);
        }
        else printf("FOREVER\n");
    }
    return 0;
}