[ABC249D] Index Trio Solution

更好的阅读体验戳此进入

题面

给定序列 $a_n$$a_n$，求满足 ${\displaystyle \frac{a_i}{a_j}}=a_k,1\le i,j,k\le n$$\dfrac{a_i}{a_j} = a_k, 1 \le i, j, k \le n$ 的不同三元组 $(i,j,k)$$(i, j, k)$ 的个数。

Solution

不难想到，原题式子不好处理，转换为 $a_j\times a_k=a_i$$a_j \times a_k = a_i$，于是不难想到一定满足 $a_j\mid a_i$$a_j \mid a_i$，并且发现值域很小，所以显然建桶，$bu{c}_i$$buc_i$ 表示值为 $i$$i$ 的数量。不难想到 $O(n)$$O(n)$ 枚举值域里每个数，然后再枚举值域范围内其所有倍数，每次枚举的贡献即为 $bu{c}_i\times bu{c}_j\times bu{c}_k$$buc_i \times buc_j \times buc_k$。

然后不难发现这东西就是个埃筛，所以复杂度显然 $O(n\log \log n)$$O(n \log \log n)$，通过调和级数等即可证明，这里略。

然后记得开 long long。

Code

xxxxxxxxxx
57
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MAX (201000)
23

24
template < typename T = int >
25
inline T read(void);
26

27
int N;
28
int a[210000];
29
int buc[210000];
30
ll ans(0);
31

32
int main(){
33
    N = read();
34
    for(int i = 1; i <= N; ++i)buc[a[i] = read()]++;
35
    for(int i = 1; i <= MAX; ++i)
36
        for(int j = 1; i * j <= MAX; ++j)
37
            ans += (ll)buc[i] * buc[j] * buc[i * j];
38
    printf("%lld\n", ans);
39
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
40
    return 0;
41
}
42

43
template < typename T >
44
inline T read(void){
45
    T ret(0);
46
    int flag(1);
47
    char c = getchar();
48
    while(c != '-' && !isdigit(c))c = getchar();
49
    if(c == '-')flag = -1, c = getchar();
50
    while(isdigit(c)){
51
        ret *= 10;
52
        ret += int(c - '0');
53
        c = getchar();
54
    }
55
    ret *= flag;
56
    return ret;
57
}

UPD

update-2022_11_30 初稿

update-2022_12_02 修改了公式里的一点细节