Как решить уравнение?
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;
}