Geometric Progression---cf 567C（求组合方式，map离散）

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

题意就是有n个数现在要让 ai aj  ak 构成公比为K的等比数列（i < j < k）;求有多少种组合方法；

我们可以对 a[i] 找 a[i]/k 和 a[i]*k ，设a[i]前面有 x个a[i]/k ;后面有y个 a[i]*k ;那么答案就是所有的x*y的和；由于数据比较大无法引用下标， 所以用map离散一下

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

#include <vector>

#include <map>

#include <string>

using namespace std;

#define INF 0x3f3f3f3f

#define met(a, b) memset(a, b, sizeof(a))

#define N 200005

typedef long long LL;

int main()

{

    int n;

    LL  k, a[N];

    while(scanf("%d %I64d", &n, &k)!=EOF)

    {

        map<LL, LL> mp1, mp2;

        for(int i=; i<=n; i++)

        {

            scanf("%I64d", &a[i]);

            mp1[a[i]]++;

        }

        LL ans = ;

        for(int i=n; i>=; i--)///倒着来便于统计mp2[x]的个数，即倒着来的数的个数；

        {

            mp1[a[i]] --;///正着来的要减减；

            if(a[i]%k==)

                ans += mp1[a[i]/k] * mp2[a[i]*k];

            mp2[a[i]] ++;

        }

        printf("%I64d\n", ans);

    }

    return ;

}

这是一个用二分写的，不用map离散化的代码；

LL a[maxn], b[maxn], l[maxn], r[maxn], n, m;

LL bin_sreach (LL x)

{

    LL high = m-, low = ;

    while (high >= low)

    {

        LL mid = (high + low) / ;

        if (b[mid] == x)

            return mid;

        if (b[mid] < x)

            low = mid + ;

        else

            high = mid -;

    }

    return n;

}

int main ()

{

    LL k;

    while (scanf ("%I64d %I64d", &n, &k) != EOF)

    {

        for (LL i=; i<n; i++)

        {

            scanf ("%I64d", &a[i]);

            b[i] = a[i];

        }

        sort (b, b+n);

        m = unique(b, b+n) - b;

        memset (l, , sizeof(l));

        memset (r, , sizeof(r));

        for (LL i=; i<n; i++)

        {

            LL x = bin_sreach(a[i]);

            l[x] ++;

        }

        __int64 ans = ;

        for (LL i=n-; i>=; i--)

        {

            LL x, y, z;

            x = y = n;

            z = bin_sreach(a[i]);

            l[z] --;

            if (a[i] % k == )

                x = bin_sreach(a[i]/k);

            y = bin_sreach(a[i]*k);

            ans += l[x] * r[y];

            r[z] ++;

        }

        printf ("%I64d\n", ans);

    }

    return ;

}