时间限制: 1000 ms         内存限制: 524288 KB

【题目描述】

原题来自：CTU Open 2004

对于 C 语言的

 

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

 

循环语句，问在 k 位存储系统中循环几次才会结束。若在有限次内结束，则输出循环次数。否则输出死循环。

【输入】

多组数据，每组数据一行四个整数 A,B,C,k。k 表示 k 位存储系统。

读入以0 0 0 0 0 结束。

【输出】

若在有限次内结束，则输出循环次数。否则输出 FOREVER。

【输入样例】

3 3 2 163 7 2 167 3 2 163 4 2 160 0 0 0

【输出样例】

0232766FOREVER

【提示】

数据范围与提示：

对于全部数据，1≤k≤32,0≤A,B,C<2^k 。

 

sol：看上去有点厉害其实不就是个Exgcd板子吗。

A+C*p1 = B (%Mod) Mod=2^k

C*p1+Mod*p2 = B-A (类ax+by=c的形式)

求p1

/*    A+C*p1 = B (%Mod) Mod=2^k    C*p1+Mod*p2 = B-A (类ax+by=c的形式)    求p1*/#include 
      
       using namespace std;typedef long long ll;inline ll read(){    ll s=0;    bool f=0;    char ch=' ';    while(!isdigit(ch))    {        f|=(ch=='-'); ch=getchar();    }    while(isdigit(ch))    {        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();    }    return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){    if(x<0)    {        putchar('-'); x=-x;    }    if(x<10)    {        putchar(x+'0');    return;    }    write(x/10);    putchar((x%10)+'0');    return;}#define W(x) write(x),putchar(' ')#define Wl(x) write(x),putchar('\n')inline ll gcd(ll x,ll y){    return (!y)?(x):(gcd(y,x%y));}inline void Exgcd(ll a,ll b,ll &X,ll &Y){    if(b==0)    {        X=1;        Y=0;        return;    }    Exgcd(b,a%b,X,Y);    ll XX=X,YY=Y;    X=YY;    Y=XX-a/b*YY;    return;}int main(){    ll A,B,C,k,Mod;    while(true)    {        R(A); R(B); R(C); R(k);        if(!(A+B+C+k)) break;        Mod=(1ll<
       
        =0)?(X%tmp):(X%tmp+tmp);        Wl(X);    }    return 0;}/*input3 3 2 163 7 2 167 3 2 163 4 2 160 0 0 0output0232766FOREVER*/