扩展欧几里得算法

给予两个整数a b，必存在整数x、y使得ax + by = gcd(a,b)
在求得一组x y的同时求得gcd(a,b)
x y其中一个有可能是负数
如果a或者b是负数 那么将求出来的x/y取反即可
很多情况下等式右边并不是gcd(a,b) 因此要乘以相应的倍数 但是这个数一定是gcd(a,b)的倍数
同时求出来的 x y是这个等式的一组解 假设为x0 y0
得到方程组
x=x0+k(b/gcd(a,b))
y=y0-k(a/gcd(a,b))
要求x的最小值 我们发现 一定是在x0的基础上改变了一定倍数的b/gcd(a,b)倍 所以x的最小值就是x0%(b/gcd(a,b))

本题思路

注意这个题 是k位存储系统中 所以是存在一个循环加一圈之后相等 比如在16位系统中 一开始a=3 c=1 b每次加2 最后是能够达成条件的
a%(1<<x)可以实现k位操作系统这一条件
所以我们可以得到
(a+xc)%2^k=b
等价于
a+xc-y2^k=b
等价于
xc-y*2^k=b-a
只有 x y 两个未知量 因此使用扩展欧几里得算法
求出gcd(a,b)
这时候如果求出的这个最大公约数不是b-a的倍数 那么就是无解
之后两边同时乘(b-a)/gcd(a,b)
回顾一下贝祖等式
ax+by=gcd(a,b)
这里的b 就是1<<k
因此可以用上文的结论得到
xmin=x(这个x是乘了倍数之后的x)%(b/gcd(a,b))

代码(抄的Y总的)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<int, int> PII;
const int maxn = 110;
const int INF = 0x3f3f3f3f;

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    ll a, b, c;
    int k;
    while (cin >> a >> b >> c >> k, a || b || c || k)
    {
        ll x, y;
        ll z = 1ll << k;
        ll d = exgcd(c, z, x, y); //注意传进去的参数
        if ((b - a) % d)
        {
            cout << "FOREVER" << endl;
            continue;
        }
        x *= (b - a) / d;
        z /= d;
        cout << (x%z + z) % z << endl;
    }
    return 0;
}