题目内容

对于给定的字符串$S_1S_2···S_n$(下标从$1$开始)，你需要依次执行以下操作:

• 筛选出所有位于质数位置(位置从$1$开始计数)的字符构成新字符串$s'$;

题解思路

这道题目要求我们根据给定的字符串，依次执行几个操作。题目中涉及到的关键点是处理质数位置的字符。考虑到字符串的长度可能非常大（最大长度为$2 \times 10^5$），我们需要优化质数判定部分，因此建议使用欧拉筛来找出所有质数位置。具体步骤如下：

步骤解析

1. 筛选质数位置的字符：
   • 题目要求从字符串中选择位于质数位置的字符。质数位置指的是索引是质数的那些位置（例如2、3、5、7等）。
   • 由于字符串长度最大为$2 \times 10^5$，我们可以通过欧拉筛法快速筛选出所有质数位置。