← 返回题目列表

Codeforces · 1582/G

G. Kuzya 和作业

中文机器翻译题面 查看原题

Kuzya 开始上学。他被布置了数学作业,其中有一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个长度为 $$$n$$$ 的符号数组 $$$b$$$,由符号“*”和“/”组成。

让我们表示一段 $$$[l; 的计算路径; r]$$$ ($$$1 \le l \le r \le n$$$) 的方式如下:

- 最初让$$$x=1$$$。对于从 $$$l$$$ 到 $$$r$$$ 的每个 $$$i$$$,我们将执行以下操作:如果 $$$b_i=$$$ '*',$$$x=x*a_i$$$,并且如果 $$$b_i=$$$ '/',则 $$$x=\frac{x}{a_i}$$$。我们将段 $$$[l; 的计算路径称为 $$$[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=$$$ '/' 或 $$$b_i=$$$ '*' 对于每个 $$$1 \le i \le n$$$)。

输出

打印单个整数 — 简单段 $$$[l;r]$$$ 的数量。

示例

输入 #1

3
1 2 3
*/*

输出 #1

2

输入 #2

7
6 4 10 1 2 15 1
*/*/*//

输出 #2

8