G. Kuzya and Homework

对每个数先分解质因数，每个质因数就能单独计算。那么对于同一个质因子，我们发现问题可以转为合法括号序列问题。

定义$l[i]\{l[i]\}$表示以第$i\{i\}$个数字结尾时，对于所有左端点的$pos\{pos\}$，$pos\sim i\{pos\backslash sim\; i\}$都可以构成合法区间（前提是$l[pos]=pos\{l[pos]=pos\}$）。

这么处理$l[i]\{l[i]\}$呢。开一个数组模拟栈，因为$1e6\{1e6\}$个栈直接$MLE\{MLE\}$，案例都过不了，而$vetor\{vetor\}$需要的内存比较小。存每个质因子的位置。

从$1\sim n\{1\backslash sim\; n\}$枚举$i\{i\}$，如果$s[i]\{s[i]\}$是除号，那么$l[i]=i\{l[i]=i\}$，分解质因子$p\{p\}$，接着$st[p]\mathrm{.}emplace\mathrm{\_}back(i)\{st[p].emplace\backslash \_back(i)\}$存质因子的位置。如果是除号，如果$a[i]==1\{a[i]==1\}$，$l[i]=i\{l[i]=i\}$，否则，分解质因子$p\{p\}$，弹出质因子的位置，取最小的位置当作$l[i]\{l[i]\}$。

统计答案，设$f(l,r)\{f(l,r)\}$为区间$[l,r]\{[l,r]\}$所有$l[i]\{l[i]\}$的最小值，那么答案就是满足$l==f(l,r)\{l==f(l,r)\}$的$[l,r]\{[l,r]\}$的对数。从$n\sim 1\{n\backslash sim\; 1\}$枚举$i\{i\}$，用栈维护。

code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+7,mod=998244353 ;
int mn[maxn],a[maxn],l[maxn],n;
vector<int>prime;
bool vis[maxn];
inline void init() {
	for(int i=2;i<maxn;++i) {
		if(!vis[i]) {
			prime.emplace_back(i);
			mn[i]=i;
		}
		for(auto j:prime) {
			if(i*j>=maxn) break;
			vis[i*j]=1;
			mn[i*j]=j;
			if(i%j==0) break;
		}
	}
}
vector<int>st[maxn];
void add(int x,int pos) {
	l[pos]=pos;
	while(x>1) {
		st[mn[x]].emplace_back(pos);
		x/=mn[x];
	}
}
void del(int x,int pos) {
	l[pos]=pos;
	while(x>1) {
		if(!st[mn[x]].size()) return l[pos]=0,void();
		l[pos]=min(l[pos],st[mn[x]].back());
		st[mn[x]].pop_back();
		x/=mn[x];
	}
}
char s[maxn];
struct node{
	ll l,ans;
};
int main() {
	cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
	init();
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	cin>>s+1;
	for(int i=1;i<=n;++i) {
		if(s[i]=='*') add(a[i],i);
		else del(a[i],i);
	}
	ll ans(0);
	stack<node>ss;
	for(int i=n;i;--i) {
		ll now=1;
		while(ss.size()&&ss.top().l>=l[i]) {
			now+=ss.top().ans;
			ss.pop();
		}
		ss.emplace(node{l[i],now});
		if(l[i]==i) ans+=now;
	}
	cout<<ans<<'\n';
	return 0;
}