种树

Luogu
IDLGP9836
Time1000ms
Memory512MB
DifficultyP4
数学贪心洛谷原创O2优化洛谷月赛
路边有 $n$ 棵树,每棵树的 **高度** 均为正整数,记作 $p_1, p_2 \dots p_n$。 定义一棵树的 **宽度** 为它高度的正因数个数,这些树能覆盖的距离为它们宽度的乘积,你想请你的朋友们来乘凉,但你发现这些树能覆盖的距离不够多。 于是你买了总量为 $w$ 单位的神奇化肥。你可以施若干次肥,每次你可以使用 $k$ 单位化肥(**要求 $k$ 必须为当前化肥量的正因数**),让任意一棵树的高度乘上 $k$,同时你剩余的化肥量也会除以 $k$。每次施肥的树可任意选择,且每次施肥选择的树不需相同。 你需要最大化这些树所能覆盖的距离,并输出这个最大距离。答案对 $998244353$ 取模。 ## Input 从标准输入中读入数据。 第一行,两个正整数 $n$ 与 $w$。 第二行 $n$ 个正整数 $p_1, p_2 \dots p_n$。 ## Output 输出到标准输出。 仅一行一个整数,代表答案对 $998244353$ 取模后的结果。 [samples] ## Background 小 Rf 不是很喜欢种花,但是他喜欢种树。 ## Note **【样例 1 解释】** + 第一次施肥,向第一棵树施 $15$ 单位的肥,使其高度变成 $120$,剩余 $4$ 单位的化肥。 + 第二次施肥,向第二棵树施 $4$ 单位的肥,使其高度变成 $972$,剩余 $1$ 单位的化肥。 + 这时候,三棵树的宽度分别为 $16, 18, 8$,所能覆盖的距离为 $2304$,为最优解。 --- **【样例 2】** 见附件下的 $\texttt{plant/plant2.in}$ 与 $\texttt{plant/plant2.ans}$。 --- **【样例 3】** 见附件下的 $\texttt{plant/plant3.in}$ 与 $\texttt{plant/plant3.ans}$。 --- **【数据范围】** | 测试点编号 | $n \leq$ | $p_i$ | $w$ | 单点分值 | | :--------: | :------: | :---: | :---: | :------: | | $1 \sim 5$ | $10^4$ | $=1$ | $=1$ | $1$ | | $6 \sim 10$ | $10^4$ | $\leq 10^4$ | $=1$ | $3$ | | $11 \sim 15$ | $1$ | $\leq 10^4$ | $\leq 10^4$ | $3$ | | $16 \sim 20$ | $5$ | $\leq 10^4$ | $\leq 10^4$ | $6$ | | $21 \sim 25$ | $10^4$ | $\leq 10^4$ | $\leq 10^4$ | $7$ | 对于 $100 \%$ 的数据,保证 $1 \leq n \leq 10^4$,$1 \leq p_i \leq 10^4$,$1 \leq w \leq 10^4$。
Samples
Input #1
3 60
8 243 250
Output #1
2304
API Response (JSON)
{
  "problem": {
    "name": "种树",
    "description": {
      "content": "路边有 $n$ 棵树,每棵树的 **高度** 均为正整数,记作 $p_1, p_2 \\dots p_n$。 定义一棵树的 **宽度** 为它高度的正因数个数,这些树能覆盖的距离为它们宽度的乘积,你想请你的朋友们来乘凉,但你发现这些树能覆盖的距离不够多。 于是你买了总量为 $w$ 单位的神奇化肥。你可以施若干次肥,每次你可以使用 $k$ 单位化肥(**要求 $k$ 必须为当前化肥量的正因数**)",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9836"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "路边有 $n$ 棵树,每棵树的 **高度** 均为正整数,记作 $p_1, p_2 \\dots p_n$。\n\n定义一棵树的 **宽度** 为它高度的正因数个数,这些树能覆盖的距离为它们宽度的乘积,你想请你的朋友们来乘凉,但你发现这些树能覆盖的距离不够多。\n\n于是你买了总量为 $w$ 单位的神奇化肥。你可以施若干次肥,每次你可以使用 $k$ 单位化肥(**要求 $k$ 必须为当前化肥量的正因数**)...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments