[CodeForces 567C] Geometric Progression

题目链接：http://codeforces.com/problemset/problem/567/C

AC代码：

/*
 * 枚举中值a[i]，然后开一个mp1维护中值前的a[i]/k这个数的个数，
 * 再开一个mp2维护中值后的a[i]*k这个数的个数，2者相乘即是等比数列的个数。
 */

#include <cstdio>
#include <map>
#include <cstring>

using namespace std;

typedef long long ll;

map<ll, int> map1;
map<ll, int> map2;

int n;
ll arr[200005], k;
ll ans;

int main() {
    while (scanf("%d%lld", &n, &k) != EOF) {
        ans = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &arr[i]);
            map2[arr[i]]++;
        }
        map1[arr[1]]++;
        map2[arr[1]]--;
        for (int i = 2; i < n; i++) {
            map2[arr[i]]--;
            if (arr[i] % k == 0) {
                ans += (ll)map1[arr[i] / k] * (ll)map2[arr[i] * k];
            }
            map1[arr[i]]++;
        }
        printf("%lld
", ans);
        map1.clear();
        map2.clear();
        memset(arr, 0, sizeof(arr));
    }
    return 0;
}