P13950 [EC Final 2019] Value

$\textit{Pang}$ 认为“要做蛋卷，必先打破鸡蛋”。 对于集合 $\{1,2,\ldots,n\}$ 的一个子集 $A$，我们按照如下方式计算 $A$ 的得分： - 初始得分为 $0$。 - 对于任意 $i\in A$，将 $a_i$ 加入得分。 - 对于任意满足 $i\ge 2$、$j\ge 2$、$i\in A$ 且 $j\in A$ 的整数对 $(i, j)$，如果存在正整数 $k>1$ 使得 $i^k = j$，则从得分中减去 $b_j$。 请你求出所有 $A$ 的最大可能得分。

第一行包含一个整数 $n$，表示元素个数 $(1\le n\le 100000)$。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个元素的加分值 $(1\le a_i\le 1000000000)$。 第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$，表示每个元素的扣分值 $(1\le b_i\le 1000000000)$。

输出一个整数 $x$，表示最大可能得分。

由 ChatGPT 4.1 翻译