A16547 | $Shiori Miyagi and Maximum Array Score$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

“Sendai，你是笨蛋吗？” ——宫城咏 只需花费 5000 日元，宫城就能让 Sendai 做任何她想做的事！今天，宫城要求 Sendai 帮她构造一个数组……不过她只想要一种非常特殊的数组。 对于任意整数 $b \geq 2$ 和 $x \geq 1$，定义 $v(b, x)$ 为满足 $b^k \mid x$ 的最大 $k$；也就是说，最大的 $k$ 使得 $x$ 是 $b^k$ 的倍数。可以证明，这个值总是一个定义良好的非负整数。 给定整数 $n$ 和 $m$，满足 $n \leq m$。请你在所有满足下述条件的长度为 $n$ 的数组 $a$ 中，找到 $\sum_{i=2}^n v(i, a_i)$ 的最大值： - $a$ 严格递增；即对于所有 $1 \leq i \leq n-1$，都有 $a_i < a_{i+1}$； - 对于所有 $1 \leq i \leq n$，都有 $1 \leq a_i \leq m$。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的组数。 每个测试用例一行，包含两个整数 $n$ 和 $m$（$2 \leq n \leq m \leq 2 \times 10^5$）。 保证所有测试用例中 $m$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示在所有满足条件的长度为 $n$ 的数组 $a$ 中，$\sum_{i=2}^n v(i, a_i)$ 的最大值。

输入 #1

输出 #1

C++ 编辑器

输入

输出