Здравствуйте. Долго думал над этой задачей, но решения не придумал. Подскажите, пожалуйста, как можно решить эту задачу.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
01:43:43
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
01:43:43
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 2 | atcoder_official | 163 |
| 4 | maomao90 | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.11.2024 15:51:18 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Где задача Renyxa ? Семь простых чисел
Если по ссылке не видно, то прочитайте так.
Алпай будет выступать на танцевальном соревновании. После выступления каждый из 7 членов жюри выставляет положительную оценку. Сумма этих оценок является общим баллом.
Алпай считает выступление хорошим, если его общий балл будет равен N. Он же считает выступление идеальным, если выступление будет хорошим и каждая оценка от жюри будет простым числом.
Для заданного N требуется найти пример оценок жюри идеального выступления.
Формат входного файла
В первой строке входного файла задается одно положительное целое число N (5 <= N <= 1015).
Формат выходного файла
Если решение существует, выведите семь простых чисел, разделенных пробелом, в порядке не убывания. Из различных решений выбирать с наименьшими простыми числами. Если решение не существует, выведите “-1”.
Или попробуйте по этой ссылке.
Брутфорс в лоб. Можно просто перебрать 7 переменных, инициализируя каждую двойкой. Суть в том, что любое число можно достаточно быстро разбить на сумму двух простых. Следовательно ответ можно представить, как
N = 5 * 2 + a + b, a > 2, b > 2в случае четногоN, иN = 4 * 2 + 3 + a + bв случае нечетного.Одно замечание. В условии недочёт ( только что заметил ). Ограничения не N (5 <= N <= 1015), а N (5 <= N <= 10^15)
Это древний баян, в оригинальной версии ограничения такие же
А как найти a и b при данных ограничениях, ибо при больших N выдаёт тайм лимит ?
Для маленьких N пишешь тупое решение. Для больших: Находишь ближайшее простое число, меньшее N, пусть оно будет A, тогда тебе нужно представить число N — A в виде суммы 6 простых чисел, то есть ты запускаешь тупое решение. Если N — A < 12, то нужно взять меньшее A. Вот, почитай тут
Решение GoToCoding не подходит, ибо не учитывается условие "Из различных решений выбирать с наименьшими простыми числами".
Господи, это и есть решение для
N <= 10^15Спасибо большое. Но как найти a и b ?
Перебор A.
B = N — A.
Быстро найдется такое A, что N-A простое.
Есть теория что любое четное число можно представить в виде суммы двух простых чисел. Используя это знание можно решить задачу. вот код
Выводишь 5 двоек если N четное или 4 двойки и одну тройку,если иначе.Минусуешь от изначального значения N,10 если оно четное или 11 ,если иначе.После используя гипотезу Гольдбаха представляешь число в виде двух простых
вот ссылка на гипотезу
вот код
Спасибо всем большое.
Что за проверка на простоту??))