题解 | 牛客周赛 Round 44 D #因子区间#
D 因子区间
首先，1e5之内的数最多拥有128个因子，所以可以从 1 ~ 128 枚举因子个数，分别计算。
对于每个因子数记录下来该因子数对应的原数组中每个数的下标，二分找到范围内的个数后利用组合数进行计算。时间复杂度
在这之前，可以 预处理1e5内每个数的因子个数.
int n, q;
void solve() {
cin >> n >> q;
vector<int> f(maxn, 0); // f[i] 数i的因子数
for (int i = 1; i <= 100000; i ++) {
for (int j = i; j <= 100000; j += i) {
f[j] += 1;
}
}
vector<vector<int>> pos(130);
for (int i = 1; i <= n; i ++) {
int x;
cin >> x;
x = f[x];
pos[x].push_back(i);
}
while (q --) {
int l, r;
cin >> l >> r;
ll res = 0;
for (int i = 1; i <= 128; i ++) {
auto it1 = upper_bound(all(pos[i]), r);
auto it2 = lower_bound(all(pos[i]), l);
int u = it1 - it2;
res += (ll)u * (u - 1) / 2;
}
cout << res << '\n';
}
}
查看35道真题和解析