题解 #342 【割】
岚雪
2018-10-31 16:10:58
## Description：
给出$n$个数$a_1,a_2,...,a_n$，询问有多少个三元组$(i, j, k)$满足以下两个条件：
- $i < j < k$；
- ${a_i}\times{a_j}\times{a_k}$是p的倍数。
## Input：
第一行两个数$n, p$。
接下来一行$n$个数。
## Output：
一行一个数表示答案。
## Sample Input：
27 360
269 154 94 221 171 154 50 210 258 358 121 159 8 47 290 125 291 293 338 248 295 160 268 227 99 4 27
## Sample output：
145
## Hint：
时间：1s 空间：512M
对于$30\%$的数据：$n \leq 100$。
对于$60\%$的数据：$n \leq 2000, 1 \leq ai \leq 10^8$。
对于$100\%$的数据：$n \leq 30000, 1 \leq ai \leq 10^8, 1 \leq p \leq 10^6$。
---
啊……简直是大水题……
首先……注意到$x\in[1,10^6]$的范围中$\text{d}_0(x)$的最大值为$120$，当$n=72\text w$时取到。
然后呢……如果$a_i$中有$p$没有的质因子，那这些质因子肯定对答案没有贡献，所以我们在读入的时候就把每个$a_i$和$p$求一个最大公约数，记进$b_i$，即$b_i=\gcd(a_i,p);$。
然后就能得出数组$b$中至多有$120$种不同的元素，枚举其中每种元素，设第$i$种元素为$c_i$，共有$d_i$个，那么若${c_i}\times{c_j}\times{c_k}\text{ mod }p=0$，就有${d_i}\times{d_j}\times{d_k}$种方式，这里$O(n^3)$枚举即可。
注意一下$a_i\times a_i\times a_i$和$a_i\times a_j\times a_j$的情况，特判即可。
```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100005
long long gcd(long long a, long long b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
long long n, p;
long long ans;
long long a[N], b[N], num[N], prime[N], cnt;
int main() {
scanf("%lld%lld", &n, &p);
for (int i = 1; i <= n; i ++) {
scanf("%lld", &a[i]);
b[i] = gcd(p, a[i]);
}
qsort(b + 1, n, sizeof(b[1]), cmp);
for (int i = 1, pointer; i <= n; i ++) {
pointer = i;
while (b[pointer] == b[i])
pointer ++;
prime[++ cnt] = b[i];
num[b[i]] = pointer - i;
i = pointer - 1;
}
for (int i = 1; i <= cnt; i ++)
if (prime[i] * prime[i] % p * prime[i] % p == 0) {
if (num[prime[i]] - 2 > 0)
ans += 1ll * num[prime[i]] * (num[prime[i]] - 1) * (num[prime[i]] - 2) / 6;
}
for (int i = 1; i <= cnt; i ++)
for (int j = 1; j <= cnt; j ++) {
if (i == j)
continue;
if (prime[i] * prime[i] % p * prime[j] % p == 0) {
if (num[prime[i]] - 1 > 0)
ans += 1ll * num[prime[i]] * (num[prime[i]] - 1) / 2 * num[prime[j]];
}
}
for (int i = 1; i <= cnt; i ++)
for (int j = i + 1; j <= cnt; j ++)
for (int k = j + 1; k <= cnt; k ++)
if (prime[i] * prime[j] % p * prime[k] % p == 0)
ans += 1ll * num[prime[i]] * num[prime[j]] * num[prime[k]];
printf("%lld\n", ans);
return 0;
}
```