# _yxl_gl_的博客

### 题解 #342 【割】

posted on 2018-10-31 16:10:58 | under 题解 |

## Description：

• $i < j < k$ ；

• ${a_i}\times{a_j}\times{a_k}$ 是p的倍数。

## 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：

#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;
}