_yxl_gl_的博客

_yxl_gl_的博客

题解 #342 【割】

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

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$ 的情况,特判即可。

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