The 21st Hunan Provincial Collegiate Programming Contest——2025-湖南省赛-H. Prime Segments

题目大意

题目描述
给定一个长度为 $n$ 的正整数序列 $a$。
求该序列中有多少个连续子段的和为素数。换言之，计算满足 $1 \le l \le r \le n$ 且 $\sum_{i=l}^r a_i$ 为素数的数对 $(l, r)$ 的数量。

输入格式
第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。
每个测试用例包含两行：
第一行为一个整数 $n$（$1 \le n \le 10^6$），表示序列的长度。
第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$，且单组测试数据内 $\sum a_i \le 10^6$），表示序列的元素。
保证同一个文件内所有测试用例的 $n$ 的总和不超过 $10^6$，所有测试用例的 $\sum a_i$ 的总和不超过 $10^6$。

输出格式
对于每个测试用例，输出一行一个整数，表示和为素数的子段数量。

样例

输入：

2
4
1 2 3 4
12
1 1 4 5 1 4 1 9 1 9 8 10

输出：

5
16

样例解释
在第一个样例中，满足条件的 $(l,r)$ 数对如下：
$l=1, r=2$：该子段的和为 $3$。
$l=2, r=2$：该子段的和为 $2$。
$l=2, r=3$：该子段的和为 $5$。
$l=3, r=3$：该子段的和为 $3$。
$l=3, r=4$：该子段的和为 $7$。

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）