ВР
решите задачку эту, потом дам ответ, будете вшоке наверно)
Size: a a a
2020 September 01
ВР
и мне кажется если научится таким фишкам, можно открывать новую математику.
ЕС
Кратные 3 могу: n/3-1, n/3, n/3+1
ЕС
Осталось 1/3 всех чисел заифать
ВР
вот интересно еслиб ком могбы думать, и он жилбы в нашем мире, какая у него былабы математика?)
ЕС
Кратные 3 могу: n/3-1, n/3, n/3+1
И аналогично можно кратные любому нечетному p, при условии, что n / p - (p - 1) / 2 > 0
MF
Остались степени двойки
ЕС
И те числа, у которых слишком большой минимальный простой делитель. 10, например
DB
можно последовательно вычитать числа начиная с 1 из исходного числа и проверять делимость для полученного числа, которая тоже увеличивается
x = x-1 и делимость на 2
x = x-2 и делимость на 3
x = x-3 и делимость на 4
x = x-1 и делимость на 2
x = x-2 и делимость на 3
x = x-3 и делимость на 4
DB
по сути ты разбиваешь число на сумму треугольного числа со стороной N и N*C
DA
хм, видимо задача сводиться к тому, является ли число делителем степени 2-ки
DA
например 8, 16 - нельзя получить, но числа вида 8k+4 (начиная с 36) можно, используя 8 подряд. также можно получить числа, которые имеют вид 16k+8 и т.д. для нечётных ответ понятен
ЕС
Можно перебрать длину последовательности, по ней однозначно востанавливается первый элемент. Получится решение за О(sqrt(n))
ЕС
А какие числа на входе? За сколько можно решать?
ВР
А какие числа на входе? За сколько можно решать?
бесконечные числа
ВР
но я понял, что большие всегда будут тру
ВР
ну или на тестах так повезло, что большие были тру.
ЕС
Тут пишут, что для степеней 2 — false
k
Виталий Рабош
но я понял, что большие всегда будут тру
ответ же скинули, что степени двойки - false, остальные true