Задача C. Есть ли прогрессия? ≡

Автор:И. Бураго, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:50  

Условие

Даны целые положительные числа S и k. Требуется найти такие целые положительные числа a и b, что:

  1. a ≤ k ≤ b
  2. Сумма всех целых чисел от a до b включительно равна S

Формат входного файла

Входной файл содержит числа S k.

Формат выходного файла

В выходном файле должны содержаться числа a b, если решение существует, и число 0 в противном случае. Если решений несколько, вывести решение с минимальным значением a.

Ограничения

1 ≤ k ≤ S ≤ 2 × 109

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
12 4
 
3 5
2 
13 12
 
0

Разбор

Согласно формуле суммы арифметической прогрессии, сумма всех чисел от a до b равна (a + b)(b − a + 1) / 2.

Частичное решение (сложность O(k))

Перебирая все a от 1 до k, мы можем вычислить b из квадратного уравнения b2 + b + ( − 2S − a2 + a) = 0. Если значение b получилось целым, и b ≥ k, то a b — решение задачи. Порядок перебора гарантирует, что первое найденное решение будет содержать минимальное значение a.

Решение (сложность O(S1 / 2))

Переберём все разложения вида 2S = x × y. Из значений x и y решением системы линейных уравнений легко получаются a и b. Если a и b — целые, и a ≤ k ≤ b, то решение найдено. Правильно выбрав порядок перебора делителей 2S, можно обеспечить минимальное значение a в первом найденном решении.

0.037s 0.005s 13