B. Свойства рядов

@LiSteNight · Регистрация: 16.01.2022

Студворк — интернет-сервис помощи студентам

B. Свойства рядов
Ограничение времени 2 секунды
Ограничение памяти 64.0 Мб

В ходе изучения присланных ЦОД данных была замечена интересная закономерность. Так были получены следующие данные:
9 + 10 + 11 + 12 = 13 + 14 + 15 (p = 4, q = 3)
4 + 5 + 6 + 7 + 8 = 9 + 10 + 11 (p = 5, q = 3)
Вы сделали вывод, что сумма p последовательных положительных целых чисел иногда равна сумме следующих q последовательных положительных чисел. Вас как исследователя заинтересовала такая закономерность и Вы решили найти для заданного q, сколько существует подходящих p.

Формат ввода
Во входном файле записано одно целое число q (1 ⩽ q ⩽ 10^14).

Формат вывода
Выведите одно число — количество подходящих значений p.

Пример
Ввод
5
Вывод
3

Я пытался вывести формулу для перебора, но в ней всегда приходится возводить q в квадрат, а из-за ограничения в q = 10^14 сто процентов будет переполнение. Тем более, перебор зайдет, только если асимптотика будет максимум О(sqrt(q)), но у меня получается сделать только за О(q)

@abit · 13.01.2023, 22:26

Не надо никаких переборов задача за О(1) решается, слева сумма арифметической прогрессии, справа тоже, приравнять их и выйдет уравнение p(q)

@LiSteNight · 13.01.2023, 23:25 **[ТС]**

Как сделать это за О(1)? Нужно найти кол-во возможных значений, и как найти их без перебора я не понимаю. Тем более, что даже если работать с формулой суммы прогрессии, там все равно получается перебор + возведение в квадрат 10^14

@SmallEvil · 13.01.2023, 23:45

Сообщение от LiSteNight

возведение в квадрат 10^14

Откуда берется этот квадрат ? Вы потомок Малевича ?

@LiSteNight · 13.01.2023, 23:55 **[ТС]**

Смешно, но нет. (n+(n+p-1))*p/2 = ((n+p)+(n+p+q-1))*q/2, где n - первый элемент прогрессии. Если раскрыть скобки, то мы и получаем в формуле несколько квадратов. Я никак не могу избавиться от квадрата и перебора значений p

@SmallEvil · 14.01.2023, 00:04

Сообщение от LiSteNight

Я никак не могу избавиться от квадрата и перебора значений p

Я не говорил ничего про O(1), но в упор не вижу квадрата (q).
Да и формулы, на глаз, непонятны.
Из чего они выведены, какая ваша логика решения ?

@zayats80888 · 14.01.2023, 00:18

LiSteNight, Последовательные суммы

@abit · 14.01.2023, 00:54

вот тут задача H, решение того, как задумали авторы на стр. 40

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

B. Свойства рядов

Решение

Решение

@LiSteNight 0 / 0 / 0 Регистрация: 16.01.2022 Сообщений: 6

	B. Свойства рядов 13.01.2023, 21:28. Показов 7484. Ответов 7 Метки c++, python, найти значение, олимпиада, олимпиадная задача, сумма, сумма ряда (Все метки) B. Свойства рядов Ограничение времени 2 секунды Ограничение памяти 64.0 Мб В ходе изучения присланных ЦОД данных была замечена интересная закономерность. Так были получены следующие данные: 9 + 10 + 11 + 12 = 13 + 14 + 15 (p = 4, q = 3) 4 + 5 + 6 + 7 + 8 = 9 + 10 + 11 (p = 5, q = 3) Вы сделали вывод, что сумма p последовательных положительных целых чисел иногда равна сумме следующих q последовательных положительных чисел. Вас как исследователя заинтересовала такая закономерность и Вы решили найти для заданного q, сколько существует подходящих p. Формат ввода Во входном файле записано одно целое число q (1 ⩽ q ⩽ 10^14). Формат вывода Выведите одно число — количество подходящих значений p. Пример Ввод 5 Вывод 3 Я пытался вывести формулу для перебора, но в ней всегда приходится возводить q в квадрат, а из-за ограничения в q = 10^14 сто процентов будет переполнение. Тем более, перебор зайдет, только если асимптотика будет максимум О(sqrt(q)), но у меня получается сделать только за О(q) 0

@abit 868 / 527 / 148 Регистрация: 03.02.2013 Сообщений: 1,845
	13.01.2023, 22:26
	Не надо никаких переборов задача за О(1) решается, слева сумма арифметической прогрессии, справа тоже, приравнять их и выйдет уравнение p(q) 0

@LiSteNight 0 / 0 / 0 Регистрация: 16.01.2022 Сообщений: 6
	13.01.2023, 23:25 [ТС]
	Как сделать это за О(1)? Нужно найти кол-во возможных значений, и как найти их без перебора я не понимаю. Тем более, что даже если работать с формулой суммы прогрессии, там все равно получается перебор + возведение в квадрат 10^14 0

@LiSteNight 0 / 0 / 0 Регистрация: 16.01.2022 Сообщений: 6
	13.01.2023, 23:55 [ТС]
	Смешно, но нет. (n+(n+p-1))p/2 = ((n+p)+(n+p+q-1))q/2, где n - первый элемент прогрессии. Если раскрыть скобки, то мы и получаем в формуле несколько квадратов. Я никак не могу избавиться от квадрата и перебора значений p 0

@zayats80888 6352 / 3523 / 1428 Регистрация: 07.02.2019 Сообщений: 8,995
	14.01.2023, 00:18
	Сообщение было отмечено LiSteNight как решение Решение LiSteNight, Последовательные суммы 1

@abit 868 / 527 / 148 Регистрация: 03.02.2013 Сообщений: 1,845
	14.01.2023, 00:54
	Сообщение было отмечено LiSteNight как решение Решение вот тут задача H, решение того, как задумали авторы на стр. 40 1