[题解] CF818E Card Game Again

前言

题目链接：洛谷

题目链接：CodeForces

题意

给定 (n) 个数 (a_1) ~ (a_n) ，与 (k) 。问有多少个区间 ([l,r]) 的积能被 (k) 整除。

两个区间不同当且仅当 (l) 不同或 (r) 不同。

思路

可以枚举左端点，然后去找满足条件的右端点。

首先将 (k) 分解质因数。

可以发现， (a_i) 分解质因数后，只有和有 (k) 相同的质因数才有用，否则对于答案是没有贡献的。那么就可以将有用的质因数给用桶给统计起来。

再将这些桶进行前缀和。可以在 (O(log n)) 的时间复杂度内求出所有的对整除影响的质数有多少。

在这个区间内，若对于每个质数的个数均大于 (k) 分解后对应质数的个数，则代表这个区间可以整数 (k) 。

那么只要枚举左区间，都可以二分出右区间。

因为一个数 (b) 最多只有 (log b) 个质因子，所以总的时间复杂度为 (O(nlog nlog k+sqrt k))

Code

#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;
namespace Quick_Function {
	template <typename Temp> void Read(Temp &x) {
		x = 0; char ch = getchar(); bool op = 0;
		while(ch < '0' || ch > '9') { if(ch == '-') op = 1; ch = getchar(); }
		while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
		if(op) x = -x;
	}
	template <typename T, typename... Args> void Read(T &t, Args &... args) { Read(t); Read(args...); }
	template <typename Temp> Temp Max(Temp x, Temp y) { return x > y ? x : y; }
	template <typename Temp> Temp Min(Temp x, Temp y) { return x < y ? x : y; }
	template <typename Temp> Temp Abs(Temp x) { return x < 0 ? (-x) : x; }
	template <typename Temp> void Swap(Temp &x, Temp &y) { x ^= y ^= x ^= y; }
}
using namespace Quick_Function;
#define int long long
#define mkp(x, y) make_pair(x, y)
const int MAXN = 1e5 + 5;
vector<pair<int, int> > vec;
int a[MAXN], n, k;
int cnt[MAXN][50], ans;
bool Check(int l, int r) {
	for(int i = 0; i < vec.size(); i++)
		if(cnt[r][i] - cnt[l - 1][i] < vec[i].second) return 0;
	return 1;
}
signed main() {
	Read(n, k); a[n + 1] = k;
	for(int i = 1; i <= n; i++) Read(a[i]);
	for(int i = 2; i <= sqrt(k); i++) {
		if(k % i == 0) vec.push_back(mkp(i, 0));
		while(k % i == 0) { k /= i; vec[vec.size() - 1].second++; }
	}
	if(k != 1) vec.push_back(mkp(k, 1));
	for(int i = 1; i <= n + 1; i++) {
		int tmp = a[i];
		for(int j = 0; j < vec.size(); j++) {
			cnt[i][j] = cnt[i - 1][j];
			while(tmp % vec[j].first == 0) { tmp /= vec[j].first; cnt[i][j]++; }
		}
	}
	for(int i = 1; i <= n; i++) { 
		int l = i, r = n + 1;
		while(l < r) {
			int mid = (l + r) >> 1;
			if(Check(i, mid)) r = mid;
			else l = mid + 1;
		}
		ans += n - l + 1;
	}
	printf("%lld", ans);
	return 0;
}