Задача №115377. Суммы из отрезка
Петя работает продавцом в лавке чисел. В наличии имеется бесконечное количество каждого из чисел \(l, l + 1,\ldots, r\) (при этом \(l < r\)). Когда в магазине нет покупателей, Петя от скуки берет некоторое количество чисел и считает их сумму. Обратите внимание, что Петя может брать одинаковые числа сколько угодно раз. При этом могут существовать некоторые целые положительные числа, которые он никогда не сможет получить в качестве суммы. Помогите Пете найти максимальное такое число.
Другими словами, найдите максимальное целое положительное число, которое нельзя представить в виде суммы произвольного количества целых чисел из отрезка \([l, r]\). Если с помощью этих чисел можно получить любое целое положительное число, выведите \(-1\).
Первая строка содержит одно целое число \(l\) (\(1 \le l \le 10^9\)) — левая граница отрезка.
Вторая строка содержит одно целое число \(r\) (\(1 \le r \le 10^9\)) — правая граница отрезка.
Гарантируется, что \(l < r\).
Выведите одно целое число — максимальное положительное число, которое нельзя получить в виде суммы чисел, принадлежащих отрезку. Если такого числа нет, выведите \(-1\).
Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать.
В данной задаче \(20\) тестов, помимо тестов из условия, каждый из них оценивается в \(5\) баллов. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(r \le 100\), наберут не менее \(20\) баллов.
Решения, корректно работающие при \(r \le 10^5\), наберут не менее \(50\) баллов.
В первом примере максимальное число, которое нельзя получить — \(11\). Можно показать, что все числа больше \(11\) получить можно. Например, \(13\) можно получить как \(4 + 4 + 5\).
Во втором примере число \(17\) получить нельзя, а все большие — можно.
В третьем примере в виде суммы чисел из отрезка можно представить любое целое положительное число.
4 5
11
6 8
17
1 10
-1