给定序列
不难想到,原题式子不好处理,转换为
然后不难发现这东西就是个埃筛,所以复杂度显然
然后记得开 long long
。
xxxxxxxxxx
571
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template < typename T = int >
25inline T read(void);
26
27int N;
28int a[210000];
29int buc[210000];
30ll ans(0);
31
32int 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
43template < typename T >
44inline 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}
update-2022_11_30 初稿
update-2022_12_02 修改了公式里的一点细节