Как решить уравнение?

a mod x = b mod kx
a <= b - заданы, необходимо найти минимальное x и затем минимальное k, где x >= 2 и k > 1

a, b <= 10^10 

Ответы (2 шт):

Автор решения: Zhihar

найти x надо?

ну можно наверное пойти таким путем:

a = x*m + z
b = kx*n + z

откуда

a - x*m = b - kx*n
a - b = x * (m - kn)

и

x = (b - a) / (kn - m)

Дальше перебором натуральных коэффициентов m, n можно найти x, при том, что

kn - m < b - a

Это если в лоб

→ Ссылка
Автор решения: Harry

Не уверен ни в оптимальности решения (какая уж оптимальность при переборе...), ни в правильности, но пока не предложено лучшего -

#include <iostream>

using namespace std;

pair<int,int> solve(int b, int a)
{
    for(int x = 2; x <= b-a; ++x)
    {
        int c = a % x;
        for(int k = 2; k*x <= b-c; ++k)
            if ((b-c)%(k*x) == 0) return make_pair(x,k);
    }
    return make_pair(0,0);
}


int main(int argc, char * argv[])
{
    int b, a;
    cin >> a >> b;
    auto [x,k] = solve(b,a);
    cout << "x = " << x << "  k = " << k << "\n";
    cout << a << " % " << x << " == " << a%x << endl;
    cout << b << " % " << k*x << " == " << b%(k*x) << endl;
}
→ Ссылка