要求結果為整數，我們將所有 \(a_i\) 分解質因數，對于每個質數分別考慮。

考慮對于一個左端點 \(l\)，能滿足要求的右端點一定在從 \(l\) 開始的一段連續區間中。于是我們得對于每個 \(l\) 求出 \(ans_l\) 表示那個最遠的右端點。

對于一個質數 \(p\)，假設 \(a_i\) 中有 \(k\) 個 \(p\)，如果 \(b_i\) 為乘號就在 \(i\) 這里記一個 \(k\)，否則記一個 \(-k\)。然后再做一個前綴和 \(pre\)。那么對于 \(l\)，我們要求的就是最大的 \(r\)，滿足 \(\forall k\in[l,r],pre_k-pre_{l-1}\ge 0\)。可以倒著掃，維護一個單調棧，每次在單調棧上二分。但是這樣的時間復雜度是無法承受的。我們考慮如果 \(a_i\) 中沒有 \(p\)，那么 \(i\) 這個位置的答案就是等于 \(i+1\) 的答案的。于是我們只用存儲那些包括了 \(p\) 的位置。于是就成了若干次區間的取 \(\min\)。再用并查集掃一遍即可。

先將所有質數都篩出來，時間復雜度可以承受。

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define lwrb lower_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5,inf=0x3f3f3f3f;
int n,prn,a[maxn];
int prm[maxn],pre[maxn];
int zh1[maxn],zh2[maxn];
int fa[maxn],ans[maxn];
bool npr[maxn];
string b;
vector<pii> wei[maxn],cun[maxn];
il void init(int x){
	for(int i=2;i<=x;i++){
		if(!npr[i]){
			prm[++prn]=i;
		}
		for(int j=i*i;j<=x;j+=i){
			npr[j]=1;
		}
	}
}
il int find(int x){
	return x!=fa[x]?fa[x]=find(fa[x]):x;
}
namespace cplx{
	bool end;
	il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>b;
	b=" "+b;
	init(1e3);
	for(int i=1,tmp;i<=n;i++){
		tmp=a[i];
		for(int j=1,cnt;j<=prn&&prm[j]<=tmp/prm[j];j++){
			if(tmp%prm[j]==0){
				cnt=0;
				while(tmp%prm[j]==0){
					tmp/=prm[j],cnt++;
				}
				wei[prm[j]].pb(mp(i,b[i]=='*'?cnt:-cnt));
			}
		}
		if(tmp>1){
			wei[tmp].pb(mp(i,b[i]=='*'?1:-1));
		}
	}
	for(int i=1,top;i<=1e6;i++){
		if(wei[i].empty()){
			continue;
		}
		pre[0]=wei[i][0].sec;
		for(int j=1;j<wei[i].size();j++){
			pre[j]=pre[j-1]+wei[i][j].sec;
		}
		top=1;
		zh1[1]=-inf,zh2[1]=n+1;
		for(int j=wei[i].size()-1,k;~j;j--){
			while(top&&zh1[top]>pre[j]){
				top--;
			}
			zh1[++top]=pre[j],zh2[top]=wei[i][j].fir;
			k=lwrb(zh1+1,zh1+top+1,pre[j]-wei[i][j].sec)-zh1-1;
			cun[zh2[k]-1].pb(mp(j?wei[i][j-1].fir+1:1,wei[i][j].fir));
		}
	}
	for(int i=1;i<=n+1;i++){
		fa[i]=i,ans[i]=n;
	}
	for(int i=0;i<=n;i++){
		for(pii j:cun[i]){
			for(int k=find(j.fir);k<=j.sec;k=find(k+1)){
				ans[k]=i;
				fa[find(k)]=find(k+1);
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		cout<<ans[i]<<" ";
//	}
//	puts("");
	ll Ans=0;
	for(int i=1;i<=n;i++){
		Ans+=ans[i]-i+1;
	}
	cout<<Ans;
	return 0;
}
}
int main(){return asbt::main();}