题解 | #C Looooops#

C Looooops

思路

k 位存储系统，意思是能储存的最大数为 2^k-1，越过了会变为 0

所以 A + x*C B（mod 2^k）
利用扩欧求得 x 即可

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;
        return a;
    }

    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;

    return d;
}

ll get_mod(ll a,ll b){
    return (a%b+b)%b;
}

int main(){
    ll A,B,C,k;

    while(cin>>A>>B>>C>>k){
        if(A==0&&B==0&&C==0&&k==0) break;

        ll a=C,b=(ll)1<<k,c=B-A;

        ll x=0,y=0;
        ll d=exgcd(a,b,x,y);

        if(c%d) puts("FOREVER");
        else{
            x*=c/d;
            x=get_mod(x,b/d);
            cout<<x<<endl;
        }
    }

    return 0;
}