【题意】对于C的for(i=A ; i!=B ;i +=C)循环语句，问在k位存储系统中循环几次才会结束。若在有限次内结束，则输出循环次数。否则输出FOREVER。

【解题思路】

           题意不难理解，只是利用了 k位存储系统 的数据特性进行循环。例如int型是16位的，那么int能保存2^16个数据，即最大数为65535（本题默认为无符号），当循环使得i超过65535时，则i会返回0重新开始计数，如i=65534，当i+=3时，i=1，其实就是 i=(65534+3)%(2^16)=1。有了这些思想，设对于某组数据要循环x次结束，那么本题就很容易得到方程： x=[(B-A+2^k)%2^k] /C，即 Cx=(B-A)(mod 2^k)  此方程为 模线性方程，本题就是求X的值。

     下面将结合红书进行简述，因此先把上面的方程变形，统一符号。令a=C  ，b=B-A ，n=2^k，那么原模线性方程变形为：ax=b (mod n)，该方程有解的充要条件为 gcd(a,n) | b ，即 b% gcd(a,n)==0，令d=gcd(a,n)，有该方程的 最小整数解为 x = e (mod n/d)，其中e = [x0 mod(n/d) + n/d] mod (n/d) ，x0为方程的最小解，那么原题就是要计算b% gcd(a,n)是否为0，若为0则计算最小整数解，否则输出FOREVER。剩下的就是套单变元模线性方程的板子了。

【AC代码】

           

#include <stdio.h>

typedef long long LL;
LL ex_gcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }else{
        LL r = ex_gcd(b,a%b,y,x);
        y-=x*(a/b);
        return r;
    }
}

int main()
{
    int A,B,C,k;
    while(scanf("%d%d%d%d",&A,&B,&C,&k)!=EOF)
    {
        if(A==0&&B==0&&C==0&&k==0)return 0;
        LL a = (LL)C;
        LL b = (LL)(B-A);
        LL n = 1LL<<k;
        LL x,y;
        int d = ex_gcd(a,n,x,y);
        if(b%d!=0)
        {
            puts("FOREVER");
        }
        else
        {
            x = (x*(b/d))%n; //ax = b(mod n)最小解
            x = ((x%(n/d)+n/d))%(n/d);//ax = b(mod n)最小整数解
            printf("%I64d\n",x);
        }
    }
    return 0;
}

【补充】单变元模线性方程板子

[说明]d = ex_gcd(a,n),先使用ex_gcd()求ax+ny=d的解，如果b不能整除d则无解，否则mod n意义下得解有d个，可以通过对某个解不断的加n/d得到。

typedef long long LL;
vector<LL>line_mod_equation(LL a,LL b,LL n)
{
    LL x,y;
    LL d = ex_gcd(a,n,x,y);
    vector<LL>ans;
    ans.clear();
    if(b%d!=0)
    {
        x%=n,x+=n,x%=n;
        ans.push_back(x*(b/d)%(n/d));
        for(LL i=1; i<d; i++)ans.push_back((ans[0]+i*n/d)%n);
    }
    return ans;
}