POJ - 2115 C Looooops

Posted on | In , ,

思路

构造线性方程cx+2^k*y=b-a，直接extgcd即可，注意对线性方程有通解计算公式:x1=x0+k*b/(gcd(a,b)),y1=y0-k*a/(gcd(a,b))。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#define ll long long
#define INF 0x7fffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))

using namespace std;

ll extgcd(ll a,ll b,ll &x,ll &y){
    ll d=a;
    if(b){
        d=extgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
    else{
        x=1,y=0;
    }
    return d;
}
int main() {
    ll a,b,c,k;
    while(~scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&k)){
        if(!a&&!b&&!c&&!k)break;
        ll x,y;
        ll tgcd=extgcd(c,(1ll<<k),x,y);
        if((b-a)%tgcd)printf("FOREVER\n");
        else{
            ll B=(1ll<<k)/tgcd,C=(b-a)/tgcd;
            printf("%lld\n",((x%B*C%B+B)%B));
        }
    }
	return 0;
}