DDOSvoid's Blog

CF 1016G Appropriate Team

发表于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/CF1016G

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和两个整数 $X$ 和 $Y$，求有多少数对 $(i,j)$ 满足存在一个整数 $v$，使得 $(v,a_i)=X$，同时 $[v,a_j]=Y$

$n\le 2\times 10^5,a_i,X,Y\le 10^{18}$

Solution

我们考虑如果存在一个数对，那么一定满足 $X|Y,X|a_i,a_j|Y$，我们令 $S$ 表示 $Y$ 的素数集合，然后我们对于每个素数单独考虑，对于一个素数 $p\in S$，我们令 $c_x$ 表示 $X$ 的次数，$c_y$ 表示 $y$ 的次数，$c_i$ 表示 $a_i$ 的次数，$c_j$ 表示 $a_j$ 的次数，那么对于 $c_x=c_y$ 的情况我们一定可以选出一个 $v$，对于 $c_x<c_y$，通过讨论我们发现，$c_i=c_x$ 和 $c_j=c_y$ 两者必须至少满足一个我们才能找到合法的 $v$

另外我们发现 $10^{18}$ 范围内的数最多只有 $15$ 个质因子，我们状压一下，相当于求 $\sum_{S\oplus T=U}f_Sg_T$，这个东西拿高维前缀和求一下即可

时间复杂度 $O(V^{\frac{1}{4}}+2^{15}15)$

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#define maxn 200010
#define ll long long
#define ull unsigned long long
using namespace std;

inline ull mul(ull x, ull y, ull p) {
    ll s = x * y - p * (ull)(1.L / p * x * y);
    return s + p * (s < 0) - p * (s >= (ll)p);
}
ll pow_mod(ll x, ll n, ll p) {
    ll s = 1;
    for (; n; n >>= 1, x = mul(x, x, p))
        if (n & 1) s = mul(s, x, p);
    return s; 
}

bool isp(ll n) {
    if (n == 1 || n % 6 % 4 != 1) return (n | 1) == 3;
    ll k = __builtin_ctzll(n - 1), m = n >> k;
    for (ll t : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
        ll p = pow_mod(t % n, m, n), i = k;
        while (p != 1 && p != n - 1 && t % n && i--) p = mul(p, p, n);
        if (p != n - 1 && i != k) return false;
    } return true;
}

ll rho(ll n) {
    auto f = [&](ll x) { return mul(x, x, n) + 1; };
    ll p = 2, q;
    for (ll i = 1, x = 0, y = 0, t = 30; t++ % 40 || gcd(p, n) == 1; x = f(x), y = f(f(y))) {
        if (x == y) x = ++i, y = f(x);
        q = mul(p, x < y ? y - x : x - y, n);
        if (q) p = q;
    } return gcd(p, n);
}

vector<ll> factorilize(ll n) {
    if (n == 1) return {};
    if (isp(n)) return {n};
    ll t = rho(n);
    auto l = factorilize(t), r = factorilize(n / t);
    l.insert(l.end(), r.begin(), r.end());
    return l;
}

int n;
ll X, Y;

ll p[20];
int cnt, cx[20], cy[20];

ll f[1 << 15], g[1 << 15];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> X >> Y;
    if (Y % X) return cout << 0 << "\n", 0;
    vector<ll> tmp = factorilize(Y);
    sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    for (auto t : tmp) p[++cnt] = t;
    ll sx = X, sy = Y;
    for (int i = 1; i <= cnt; ++i) {
        while (sx % p[i] == 0) sx /= p[i], ++cx[i];
        while (sy % p[i] == 0) sy /= p[i], ++cy[i];
    } 
    for (int o = 1; o <= n; ++o) { 
        ll x; cin >> x;
        if (x % X == 0) {
            ll t = x; int S = 0; 
            for (int i = 1; i <= cnt; ++i) {
                if (cx[i] == cy[i]) { S |= 1 << i - 1; continue; }
                int s = 0; while (t % p[i] == 0) t /= p[i], ++s;
                if (s == cx[i]) S |= 1 << i - 1; 
            } ++f[S];
        }
        if (Y % x == 0) {
            ll t = x; int S = 0; 
            for (int i = 1; i <= cnt; ++i) {
                if (cx[i] == cy[i]) { S |= 1 << i - 1; continue; }
                int s = 0; while (t % p[i] == 0) t /= p[i], ++s;
                if (s == cy[i]) S |= 1 << i - 1; 
            } ++g[S];
        }
    } int M = (1 << cnt) - 1; ll ans = 0;
    for (int o = 0; o < cnt; ++o)
        for (int S = M; ~S; --S)
            if (!(S >> o & 1)) f[S] += f[S | 1 << o];
    for (int S = 0; S <= M; ++S) ans += g[S] * f[M ^ S];
    cout << ans << "\n";
    return 0; 
}