CF1582G Kuzya and Homework

Kuzya 开始上学了。他收到了一道数学作业，作业中给出了一个长度为 $n$ 的数组 $a$ 和一个长度为 $n$ 的符号数组 $b$，$b$ 由符号 '\*' 和 '/' 组成。 我们将区间 $[l, r]$ 的计算路径定义如下： - 初始时令 $x=1$。对于每一个从 $l$ 到 $r$ 的 $i$，依次进行如下操作：如果 $b_i$ 为 '\*'，则 $x = x \times a_i$；如果 $b_i$ 为 '/'，则 $x = \frac{x}{a_i}$。我们称区间 $[l, r]$ 的计算路径为计算过程中得到的所有 $x$ 的列表（数量恰好为 $r-l+1$ 个）。 例如，设 $a=[7, 12, 3, 5, 4, 10, 9]$，$b=[/, *, /, /, /, *, *]$，$l=2$，$r=6$，那么该区间的计算路径为 $[12, 4, 0.8, 0.2, 2]$。 我们称区间 $[l, r]$ 为“简单区间”，如果其计算路径中所有的数都是整数。 Kuzya 需要你帮他找出有多少个“简单区间” $[l, r]$（$1 \le l \le r \le n$）。由于他显然没有时间和兴趣去枚举每一种情况，所以他请你写一个程序来计算这个数量！

第一行包含一个整数 $n$（$2 \le n \le 10^6$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$）。 第三行包含 $n$ 个没有空格的符号，组成数组 $b_1, b_2, \ldots, b_n$（每个 $b_i$ 都是 '/' 或 '\*'）。

输出一个整数，表示“简单区间” $[l, r]$ 的数量。

由 ChatGPT 4.1 翻译