За 5000 йен, Мияги может попросить Сэндай сделать всё, что она хочет! Сегодня Мияги требует, чтобы Сэндай составила для неё массив... конкретно, Мияги хочет очень особый тип массива.
Для произвольных целых чисел $$$b\geq 2$$$ и $$$x\geq 1$$$, определим $$$v(b, x)$$$ как максимальное $$$k$$$, удовлетворяющее $$$b^k \mid x$$$; то есть, максимальное $$$k$$$, такое что $$$x$$$ является кратным $$$b^k$$$. Можно показать, что это всегда вполне определённое, неотрицательное целое число.
Вам даны целые числа $$$n$$$ и $$$m$$$, удовлетворяющие $$$n\leq m$$$. Найдите максимальное значение $$$\sum_{i=2}^n v(i, a_i)$$$ среди всех массивов $$$a$$$ длины $$$n$$$, удовлетворяющих следующим условиям:
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2\leq n\leq m \leq 2\cdot 10^5$$$).
Гарантируется, что сумма $$$m$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число, максимальное значение $$$\sum_{i=2}^n v(i, a_i)$$$ среди всех массивов $$$a$$$ длины $$$n$$$, удовлетворяющих данным условиям.
64 206 66 2163 5002 85 29
75191339
В первом примере одним из возможных массивов является $$$a = [6, 8, 9, 16]$$$ что даёт значение $$$3 + 2 + 2 = 7$$$.
Можно показать, что это максимальное значение $$$\sum_{i=2}^n v(i, a_i)$$$ среди всех массивов $$$a$$$ длины $$$n$$$, удовлетворяющих данным условиям.
| Codeforces Round 1065 (Div. 3) |
|---|
| Закончено |
