题目链接：https://codeforces.com/contest/1582/problem/F2

这题真的想偏了23333333。先说一个性质：如[l,r]不符合条件那么任意[l,r'](r'>r)肯定都不符合条件。因为 [l,r] 序列肯定是被一处或者多处阻断，如l不动，r增大阻断点还是没有消除。所以与r+1不可匹配的l肯定对r的不可匹配l有所继承，且要多于r的不可匹配数量。那么将r的可匹配集继承给r+1，然后再把不符合条件的都删掉。

真的是一个很牛逼的解法啊

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[1000055],pmi[1000555],prime[1000555],cnt;
char b[1000555];
vector<int>v[1000555],s;
int main(){

//质因数分解
	for(int i=2;i<=1e6;i++){
		if(!pmi[i]) pmi[i]=i,prime[++cnt]=i;
		for(int j=1;j<=cnt&&prime[j]*i<=1e6;j++){
			pmi[i*prime[j]]=prime[j];
			if(i%prime[j]==0) break;
		}
	}
	ll ans=0;
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%s",b+1);
	for(int i=1;i<=n;i++){
		s.push_back(i);
		if(b[i]=='*'){
			for(int now=a[i];now!=1;now/=pmi[now]){
				v[pmi[now]].push_back(i);
			}
		}
		else{
			for(int now=a[i];now!=1;now/=pmi[now]){
				while(s.size()&&(v[pmi[now]].empty()||v[pmi[now]].back()<s.back())) s.pop_back();//弹出不符合条件的l
				if(v[pmi[now]].size()) v[pmi[now]].pop_back();//被除掉了
			}
		}
		ans+=s.size();//s是当前r=i符合条件的l集合
	}
	cout<<ans;
	return 0;
}