题解

题面描述

给定一个长度为 $n$ 的数组，每个数的权值定义为其质因子的个数（注意：质因子只计算不同的质数，例如 $4$ 的质因子只有 $2$，权值为 $1$）。现在要求删除数组中连续的一段长度恰好为 $k$ 的子数组，使得剩余数组中所有数字的权值和最大。求最大的权值和。

思路

题目内容

游游有一个长度为$n$ 的数组，每个数的权值为它的质因子个数。现在游游想要删除一段长度刚好为$k$的子数组，删除后需要使剩下的数的权值和最大。问这个权值和是多少?

输入描述

第一行两个整数$n(1 ≤n≤ 10^5),k(1≤k≤n)$。

接下来一行$n$个正整数$a_i(1≤a_i≤10^4)$。

输出描述

输出一个整数，表示答案。

样例1

输入

5 2
6 2 4 1 3

输出

4

说明

$1$没有质因子，权值为$0$。

$2$的质因子是$2$，权值为$1$。

$3$的质因子是$3$，权值为$1$。

$4$的质因子是$2$，权值为$1$。

$6$的质因子是$2$和$3$，权值为$2$。

删除子数组 $[4,1]$，剩下的数是$6,2,3$，权值总和为$4$。