Привет, Codeforces! У меня 13 успешных взломов по задаче D, а также мое решение не прошло систесты(возможно один из моих :) ) У нас есть две части решения
Первая часть посчитать для числа наименьший делитель, это делается решетом Эратосфена за O(NlogN) если просеивать всеми числами, если только простыми, то за O(NloglogN), или же линейным решетом за O(N).
Вторая часть это подсчёт ответа. Мы должны для каждого числа вида xdx+dc прибавить 2k, где k -- количество различных простых делителей. (dx делится на x). Если не предподсчитывать, то это будет O(logx) на делитель, иначе O(1).
Теперь попробуем подобрать числа c,d,x чтобы взломать решение за O(t√xlogx+NloglogN). Поскольку мы считаем количество различных простых делителей у чисел вида xdx+dc, мы будем использовать c=1. Также мы факторизуем число x. Сначала найдем x с наибольшим количеством делителей, и этот x есть 8648640. Затем попробуем максимизировать
где s(n) -- сумма степеней простых в факторизации n(именно столько операций мы делаем).
Теперь у нас есть мощный тест. 10000 раз по c=1,d=x=8648640. Ниже вы можете посмотреть взломанные таким способом решения https://mirror.codeforces.com/contest/1499/hacks/714784
https://mirror.codeforces.com/contest/1499/hacks/714699
https://mirror.codeforces.com/contest/1499/hacks/714697
https://mirror.codeforces.com/contest/1499/hacks/714692
https://mirror.codeforces.com/contest/1499/hacks/714688
https://mirror.codeforces.com/contest/1499/hacks/714629
https://mirror.codeforces.com/contest/1499/hacks/714683
Но некоторые решения не сломались, и тому много причин. Иногда люди предподсчитывали наименьшие делители сразу возведенные в степень вхождения, и тогда в среднем по Second Merten's Theorem ответ будет искаться за O(loglogx) для делителя в среднем и наше d уже не работает. Но основная проблема заключается в работе с памятью и кешем процессора, поэтому нужно генерировать различные числа с большим количеством делителей. Это можно сделать рандомом. Но как использовать рандомизированный генератор на кфе? Достаточно просто задать сид для mt19937.
Пример такого взлома
User: haruki_K
Submission: 110353111
Существуют и другие сильные взломы, например d=(3⋅5⋅7⋅11…)−x. Но также есть более странные вещи. Например три посылки(все из них мои, и все из них имеют разное время на макстесте): 110370237, 110420633, 110439475
Если вы можете это объяснить, то пожалуйста, сделайте это.
Резюмируя, я хочу сказать, что ограничения были несбалансированы, потому что люди которые придумали идею, и просто не предподсчитали ответ, получили TL. Ограничения в ОБУЧАЮЩИХ раундах не должны быть такими жесткими, особенно учитывая такую погрешность (см.выше).
Также я хочу поблагодарить plagues за отправление моего решения, чтобы порофлить надо мной :)