У коробці з рядами цукерок рівно T_r = \frac{r(r+1)}{2} штук. Треба порахувати, для скількох від до виконується M \mid T_r, тобто
Тут працює важлива властивість: \gcd(r, r+1) = 1. Розкладемо на прості множники: 2M = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}. Оскільки і r+1 взаємно прості, кожен степінь p_i^{e_i} мусить цілком поділити або , або r+1 — «розщепити» його між ними неможливо.
Отже, переберемо всі 2^t способів розділити прості степені на дві групи. Нехай добуток однієї групи дорівнює , а другої — (за побудовою \gcd(d, 2M/d) = 1). Тоді умова перетворюється на систему
За китайською теоремою про остачі така система має рівно один розв'язок за модулем ; знайти його можна розширеним алгоритмом Евкліда. Залишається порахувати, скільки чисел цієї арифметичної прогресії потрапляє у відрізок — це робиться однією формулою з цілочисельним діленням.
Просумувавши по всіх розбиттях, отримаємо відповідь. Різні розбиття дають різні остачі, тому подвійного врахування не буде.
Оцінка складності: розклад 2M \le 4 \cdot 10^8 пробними діленнями — \mathcal{O}(\sqrt{2M}), тобто близько 2 \cdot 10^4 операцій; різних простих не більше дев'яти, тому розбиттів щонайбільше . Прямий перебір усіх від до був би надто повільним при N = 2 \cdot 10^8.
Усі обчислення ведіть у 64-бітному типі: добутки сягають 4 \cdot 10^8, а проміжні значення в CRT — ще більших величин.