Kuzya and Homework

题意翻译

给定长度为 $n$ 的正整数序列 $a$，和长度为 $n$的符号序列 $b$。$b$ 是由'\*'和'/’组成的。 用下述方法计算一个区间 $[l,r]$ 的值序列： * 初始令 $x=1$.对于每一个$i (l \le i \le r)$依次进行如下操作：如果 $b_i=$'\*',令 $x=x * a_i$，如果 $b_i=$'\\',令 $x=\frac{x}{a_i}$。一个区间 $[l,r]$ 的值序列就是 $x$ 经过每一次运算后得到的序列。 比如，令 $a=[7,12,3,5,4,10,9],b=[/,*,/,/,/,*,*],l=2,r=6$，那么这个区间的值序列是 $[12,4,0.8,0.2,2]$. 给出 $a,b$，求值序列仅含整数的区间个数。

题目描述

Kuzya started going to school. He was given math homework in which he was given an array $ a $ of length $ n $ and an array of symbols $ b $ of length $ n $ , consisting of symbols '\*' and '/'. Let's denote a path of calculations for a segment $ [l; r] $ ( $ 1 \le l \le r \le n $ ) in the following way: - Let $ x=1 $ initially. For every $ i $ from $ l $ to $ r $ we will consequently do the following: if $ b_i= $ '\*', $ x=x*a_i $ , and if $ b_i= $ '/', then $ x=\frac{x}{a_i} $ . Let's call a path of calculations for the segment $ [l; r] $ a list of all $ x $ that we got during the calculations (the number of them is exactly $ r - l + 1 $ ). For example, let $ a=[7, $ $ 12, $ $ 3, $ $ 5, $ $ 4, $ $ 10, $ $ 9] $ , $ b=[/, $ $ *, $ $ /, $ $ /, $ $ /, $ $ *, $ $ *] $ , $ l=2 $ , $ r=6 $ , then the path of calculations for that segment is $ [12, $ $ 4, $ $ 0.8, $ $ 0.2, $ $ 2] $ . Let's call a segment $ [l;r] $ simple if the path of calculations for it contains only integer numbers. Kuzya needs to find the number of simple segments $ [l;r] $ ( $ 1 \le l \le r \le n $ ). Since he obviously has no time and no interest to do the calculations for each option, he asked you to write a program to get to find that number!

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2 \le n \le 10^6 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^6 $ ). The third line contains $ n $ symbols without spaces between them — the array $ b_1, b_2 \ldots b_n $ ( $ b_i= $ '/' or $ b_i= $ '\*' for every $ 1 \le i \le n $ ).

输出格式

Print a single integer — the number of simple segments $ [l;r] $ .

输入输出样例

输入样例 #1

3
1 2 3
*/*

输出样例 #1

2

输入样例 #2

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

输出样例 #2

8