考虑把每个数都分解质因数来统计。枚举右端点 ，然后维护一个栈 表示当前有哪些左端点是合法的， 表示若只考虑质因数为 的部分有哪些左端点是合法的。则此时若 位置对应的字符是 *，直接把 加入 和 中即可，否则在 和 中把 对应的质因数抵消掉。统计结束后栈 内的元素数量即为右端点为 的合法区间数量。
线性筛出 表示 的最小质因数可以做到 时间复杂度解决问题。
namespace Loyalty
{
int a[N];
char s[N];
vector<int> S[N];
int isp[N], pr[N], idx, minp[N];
inline void init() {}
inline void main([[maybe_unused]] int _ca, [[maybe_unused]] int _atc)
{
isp[1] = minp[1] = 1;
for (int i = 2; i < N; ++i)
{
if (!isp[i])
pr[++idx] = minp[i] = i;
for (int j = 1; j <= idx && i * pr[j] < N; ++j)
{
minp[i * pr[j]] = pr[j], isp[i * pr[j]] = 1;
if (i % pr[j] == 0)
break;
}
}
// cerr << "minp: ";
// for (int i = 2; i <= 25; ++i)
// cout << minp[i] << ' ';
// cout << '\n';
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
scanf("%s", s + 1);
long long res = 0;
stack<int> stk;
for (int i = 1; i <= n; ++i)
{
stk.emplace(i);
if (s[i] == '*')
{
for (int j = a[i]; j > 1; j /= minp[j])
S[minp[j]].emplace_back(i);
}
else
{
for (int j = a[i]; j > 1; j /= minp[j])
{
while (stk.size() && (S[minp[j]].empty() || stk.top() > S[minp[j]].back()))
stk.pop();
if (S[minp[j]].size())
S[minp[j]].pop_back();
}
}
res += stk.size();
}
cout << res << '\n';
}
} // namespace Loyalty
喜欢的话，留下你的评论吧～