Пусть мы нашли НОД всех смежных разностей (а также всех разностей с первым, с локально минимальным, с локально максимальным элементами — сколько угодно).
Тогда, без потери общности задачи, мы можем взять эквивалентный файл, такой, что его минимальный элемент = 0 (т.е. вычли f_min из всех элементов f), а НОД равен 1 (поделили (f-f_min) на НОД).
То есть свели задачу к такой: можно ли для набора разных неотрицательных чисел определить — является ли он арифметической прогрессией вида 0,1,2,...k...
Ответ: конечно, да!
Предположим, что у нас N чисел (и все они разные по условиям задачи; мы это утверждение дополнительно не проверяем!).
Тогда они будут являться указанной прогрессией тогда и только тогда, когда минимум = 0, а максимум = N-1.
Доказательство очевидно: пусть в наборе есть "щербина" (отсутствуют некоторые числа прогрессии). Тогда, если минимум = 0 и максимум = M-1, то количество N будет меньше, чем M.
А если щербины нет, то M==N.
Повторяться числа не могут по условию, поэтому вариант N>M, а также компенсация щербин повторами невозможна.
Теперь вернем все на место: каждый элемент натуральной прогрессии умножим на D и прибавим f_min.
Таким образом, алгоритм проверки найден:
1) находим D = НОД((f[0]-f[k]) для всех k), f_min, f_max, N
2) проверяем f_min + D*(N-1) == f_max.
В нашем доказательстве мы исходили из того, что D>0 (делили и умножали на него). Очевидно, что случай D==0 говорит о том, что одна из разностей оказалась нулевой, то есть в файле встретился повтор.
Большую часть работы ты проводишь, чтобы сказать: все числа (относительно первого) кратны шагу прогрессии, который был найден как НОД всех разностей. Это как бы масло масляное: все разности кратны НОД от их всех
Меня же как раз волновало доказательство того, что (N-1)*D=(max-min) есть необходимое и достаточное условие (которое ты упомянул всколзь).
Здравствуйте, Кодт, Вы писали:
К>Большую часть работы ты проводишь, чтобы сказать: все числа (относительно первого) кратны шагу прогрессии, который был найден как НОД всех разностей. Это как бы масло масляное: все разности кратны НОД от их всех
Просто я долго не мог понять, это очевидно или не очень
Как говорил мой школьный учитель (покайный ) "очевидное — это то, что легко доказать". Вот я и решил доказать.
К>Меня же как раз волновало доказательство того, что (N-1)*D=(max-min) есть необходимое и достаточное условие (которое ты упомянул всколзь).
Ну а это, по-моему и ежу понятно. Если шаг прогрессии может быть только D и никак иначе, то проверка сразу получается.
В общем, разница была только в том, кто что считал очевидным
Кр-ть — с.т.
Перекуём баги на фичи!
) "очевидное — это то, что легко доказать". Вот я и решил доказать. 
