Хотелось бы отметить следующее. Целевая функция

- "рваная" нелинейная из-за
gcd. Но ведь можно перейти в другую систему координат, сделав неизвестным аргументом саму матрицу
gcd:

где

- матрица фиксированных коэффициентов (квадрат дистанций между ячейками квадрата)

- матрица неизвестных
gcd, дающих искомый оптимум суммы
Тогда целевая функция становится чисто линейной, и задача превращается в линейное программирование с ограничениями, одно из которых

и учёт которого можно отложить на второй шаг. Для первого шага соорудить более простые ограничения, например количества двоек, троек, четвёрток и т.д. в таблице
gcd, которые можно посчитать заранее.