题目描述

https://www.acwing.com/problem/content/1303/

算法1

(扩展欧几里得)

分析

扩展欧几里得算法的简单应用
下面是扩展欧几里得算法的结论
当$b = 0$时, $x = 1, y = 0$
当$b != 0$时,$x = y’, y = x’ - ⌊a/b⌋ * y’$

题意抽象：$$(a + c*x) \% 2 ^k = b$$
变形：$$a + c * x - y * 2 ^ k = b$$
$$c * x - y * 2 ^ k = b - a$$
令 $$y_1 = -y$$
$$c * x + y_1 * 2 ^ k = b - a$$
由此，套用欧几里得模板求出满足$x, y$满足$c * x + y_1 * 2 ^ k = gcd(c, 2^k)$
由此，如果最大公约数$gcd(c, 2^k)$不是$b -a$的倍数, 则无解
否则， 等式两边同乘$b - a/gcd(c, 2^k)$
然后得出$x$, 和 $z = 2 ^k$乘后的结果
计算出$(x \% z + z) \% z即可$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    LL x1, y1;
    LL gcd = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - (a / b) * y1;
    return gcd;
}

int main()
{
    LL a, b, c;
    int k;
    while(cin >> a >> b >> c >> k, a || b || c || k)
    {
        LL z = 1ll << k;
        LL x, y;
        LL d = exgcd(c, z, x, y);
        if((b - a) % d)
        {
            cout << "FOREVER" << endl;
            continue;
        }
        else
        {
            x *= (b - a) / d;
            z /= d;
            cout << (x % z + z) % z << endl;
        }
    }
    return 0;
}