input
n,k 1<=n,k<=200000
a1 a2 ... an
1<=ai<=1e9
output
数组中选三个数,且三个数的下标严格递增，凑成形如b,b*k,b*k*k的种数
做法：先将可以作为第三个数的数放到map中，然后再扫一遍依次统计map中的数作为第三个数的种数，第二个数的种数，第三个数的种数
1 #include<cstdio> 2 #include<map> 3 struct node 4 { 5 int b;//a[i]作为i1的种数 6 long long c;//a[i]作为i2的种数 7 }; 8 using namespace std; 9 int a[200010], n, k; 10 long long k2, sum; 11 map<int,node>q; 12 map<int,node>::iterator j; 13 int main() 14 { 15 while (scanf("%d%d", &n, &k) == 2) 16 { 17 q.clear(); 18 k2 = (long long)k*k; 19 node u; 20 sum = u.b = u.c = 0; 21 for (int i = 0; i < n; i++) 22 { 23 scanf("%d", &a[i]); 24 if (!(a[i] % k2)) q.insert(make_pair(a[i] / k2,u));//统计出所有的i3 25 } 26 if (q.empty()) { puts("0");continue; } 27 for (int i = 0; i < n; i++) 28 { 29 if (a[i] % k2 == 0)//a[i]作为i3 30 { 31 j = q.find(a[i]/k2);//找i2 32 if(j!=q.end()) sum += j->second.c;//累加到总方法数 33 } 34 if (a[i] % k == 0)//a[i]作为i2 35 { 36 j = q.find(a[i] / k);//找i1 37 if (j != q.end()) j->second.c += j->second.b;//累加到i2的方法数 38 } 39 j = q.find(a[i]);//a[i]作为i1找i1 40 if (j != q.end()) j->second.b++;//累加 41 } 42 printf("%lld ", sum); 43 } 44 return 0; 45 }