Поиск элементов массива, когда задана сумма подмассивов

Question

Массив из N элементов имеет индекс с 1 по N. Все элементы неизвестны и являются целыми числами. Для некоторых запросов в форме A, B, C, где A - начальный индекс, B - конечный индекс, а C - сумма всех элементов между A и B включительно. Узнайте все элементы массива. Пример:

N=4
1, 3, 0
2, 4, 4

Одно из правильных решений:

2, -3, 1, 6

Ограничения:

1<=A<=B<=N, 2<=N<=65000, C<=1000000000

Любое решение, удовлетворяющее заданным критериям, принимается и предполагается, что дано достаточно запросов, чтобы выяснить все элементы.

Answer 1

Одним из способов решения этой проблемы является трактовка проблемы как серии одновременных уравнений.Каждое суммирование дает вам линейное уравнение с числом переменных до n, поэтому, если вы можете найти решение этого уравнения, которое имеет целочисленные значения, вы должны быть полностью установлены.различные ограничения требуют (при условии, что n = O (k)) O (k ³ ) времени ожидания (при условии, что система хорошо подготовлена)Оттуда найти целочисленные решения должно быть легко;просто найдите общий знаменатель любого вектора решения и умножьте его на него.

Надеюсь, это поможет!