Kuzya and Homework (Codeforces 1582G)
Tags: Others, number theory

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!

Input: 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$$$).

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


Sample Inputs:
3
1 2 3
*/*

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

Sample Outputs:
2

8

Solution (Python):
import sys, math
from collections import defaultdict
N = 1000005
maxf = [0] * N
for i in range(2, int(math.sqrt(N)) + 2):
    if maxf[i] == 0:
        for j in range(i + i, N, i):
            maxf[j] = i
for i in range(2, N):
    if maxf[i] == 0:
        maxf[i] = i
n = int(sys.stdin.readline())
a = [int(i) for i in sys.stdin.readline().split()]
p = defaultdict(list)
l = [0] * n
r = 0
for (idx, i) in enumerate(sys.stdin.readline().strip()):
    x = a[idx]
    l[idx] = idx + 1
    if i == '*':
        while x > 1:
            p[maxf[x]].append(idx + 1)
            x //= maxf[x]
    else:
        while x > 1:
            l[idx] = min(l[idx], p[maxf[x]].pop()) if p[maxf[x]] else 0
            x //= maxf[x]
st = []
for i in range(n):
    st.append(i + 1)
    while st and st[-1] > l[i]:
        st.pop()
    r += len(st)
print(r)

Solution (Python):
import sys
from math import sqrt
from collections import defaultdict
N = 1000005
maxf = [0] * N
for i in range(2, int(sqrt(N)) + 2):
    if maxf[i] == 0:
        for j in range(i + i, N, i):
            maxf[j] = i
for i in range(2, N):
    if maxf[i] == 0:
        maxf[i] = i
n = int(sys.stdin.readline())
a = [int(i) for i in sys.stdin.readline().split()]
p = defaultdict(list)
l = [0] * n
r = 0
st = []
for (idx, i) in enumerate(sys.stdin.readline().strip()):
    x = a[idx]
    l[idx] = idx + 1
    if i == '*':
        while x > 1:
            p[maxf[x]].append(idx + 1)
            x //= maxf[x]
    else:
        while x > 1:
            l[idx] = min(l[idx], p[maxf[x]].pop()) if p[maxf[x]] else 0
            x //= maxf[x]
for i in range(n):
    st.append(i + 1)
    while st and st[-1] > l[i]:
        st.pop()
    r += len(st)
print(r)

Solution (Python):
import sys
from math import sqrt
from collections import defaultdict
N = 1000005
maxf = [0] * N
for i in range(2, int(sqrt(N)) + 2):
    if maxf[i] == 0:
        for j in range(i + i, N, i):
            maxf[j] = i
for i in range(2, N):
    if maxf[i] == 0:
        maxf[i] = i
n = int(sys.stdin.readline())
a = [int(i) for i in sys.stdin.readline().split()]
p = defaultdict(list)
l = [0] * n
r = 0
st = []
for (idx, i) in enumerate(sys.stdin.readline().strip()):
    x = a[idx]
    l[idx] = idx + 1
    if i == '*':
        while x > 1:
            p[maxf[x]].append(idx + 1)
            x //= maxf[x]
    else:
        while x > 1:
            l[idx] = min(l[idx], p[maxf[x]].pop()) if p[maxf[x]] else 0
            x //= maxf[x]
for i in range(n):
    st.append(i + 1)
    while st and st[-1] > l[i]:
        st.pop()
    r += len(st)
print(r)