题目描述
https://codeforces.com/contest/691/problem/F
Solution
注意到 $p$ 很小，所以我们直接枚举 $1$ 到 $p$ 的所有数的约数
复杂度是 $O(p\log p)$ 的
由于 $a_i$ 的乘积可能很大，所以我们用总的方案减小于 $p$ 的方案比较容易计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define ll long long
#define maxn 3000010
using namespace std;
int n, m;
const int N = 3000000;
ll cnt[maxn], num[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n; ll ans = (ll) n * (n - 1);
for (int i = 1, x; i <= n; ++i) cin >> x, ++num[x];
for (int i = 1; i <= N; ++i)
for (int j = i; j <= N; j += i)
if (i == j / i) cnt[j] += num[i] * (num[i] - 1);
else cnt[j] += num[i] * num[j / i];
for (int i = 1; i <= N; ++i) cnt[i] += cnt[i - 1];
cin >> m;
for (int i = 1; i <= m; ++i) {
int x; cin >> x;
cout << ans - cnt[x - 1] << "\n";
}
return 0;
}
|