Привет, Codeforces! У меня 13 успешных взломов по задаче D, а также мое решение не прошло систесты(возможно один из моих :) ) У нас есть две части решения

Первая часть посчитать для числа наименьший делитель, это делается решетом Эратосфена за $$$O(N \log N)$$$ если просеивать всеми числами, если только простыми, то за $$$O(N \log \log N)$$$, или же линейным решетом за $$$O(N)$$$.

Вторая часть это подсчёт ответа. Мы должны для каждого числа вида $$$\frac{\frac{x}{d_x} + d}{c}$$$ прибавить $$$2^k$$$, где $$$k$$$ -- количество различных простых делителей. ($$$d_x$$$ делится на $$$x$$$). Если не предподсчитывать, то это будет $$$O(\log x)$$$ на делитель, иначе $$$O(1)$$$.

Теперь попробуем подобрать числа $$$c, d, x$$$ чтобы взломать решение за $$$O(t\sqrt{x} \log x + N \log \log N)$$$. Поскольку мы считаем количество различных простых делителей у чисел вида $$$\frac{\frac{x}{d_x} + d}{c}$$$, мы будем использовать $$$c = 1$$$. Также мы факторизуем число $$$x$$$. Сначала найдем $$$x$$$ с наибольшим количеством делителей, и этот $$$x$$$ есть $$$8648640$$$. Затем попробуем максимизировать

где $$$s(n)$$$ -- сумма степеней простых в факторизации $$$n$$$(именно столько операций мы делаем).

Теперь у нас есть мощный тест. 10000 раз по $$$c=1, d=x=8648640$$$. Ниже вы можете посмотреть взломанные таким способом решения https://codeforces.com/contest/1499/hacks/714784

https://codeforces.com/contest/1499/hacks/714699

https://codeforces.com/contest/1499/hacks/714697

https://codeforces.com/contest/1499/hacks/714692

https://codeforces.com/contest/1499/hacks/714688

https://codeforces.com/contest/1499/hacks/714629

https://codeforces.com/contest/1499/hacks/714683

Но некоторые решения не сломались, и тому много причин. Иногда люди предподсчитывали наименьшие делители сразу возведенные в степень вхождения, и тогда в среднем по Second Merten's Theorem ответ будет искаться за $$$O(\log \log x)$$$ для делителя в среднем и наше $$$d$$$ уже не работает. Но основная проблема заключается в работе с памятью и кешем процессора, поэтому нужно генерировать различные числа с большим количеством делителей. Это можно сделать рандомом. Но как использовать рандомизированный генератор на кфе? Достаточно просто задать сид для mt19937.

Пример такого взлома

User: haruki_K

Submission: 110353111

Существуют и другие сильные взломы, например $$$d = (3 \cdot 5 \cdot 7 \cdot 11 \dots) - x$$$. Но также есть более странные вещи. Например три посылки(все из них мои, и все из них имеют разное время на макстесте): 110370237, 110420633, 110439475

Если вы можете это объяснить, то пожалуйста, сделайте это.

Резюмируя, я хочу сказать, что ограничения были несбалансированы, потому что люди которые придумали идею, и просто не предподсчитали ответ, получили TL. Ограничения в ОБУЧАЮЩИХ раундах не должны быть такими жесткими, особенно учитывая такую погрешность (см.выше).

Также я хочу поблагодарить plagues за отправление моего решения, чтобы порофлить надо мной :)