C. Geometric Progression
Time Limit: 2 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/567/problem/C
Description
Polycarp loves geometric progressions very much. Since he was only three years old, he loves only the progressions of length three. He also has a favorite integer k and a sequence a, consisting of n integers.
He wants to know how many subsequences of length three can be selected from a, so that they form a geometric progression with common ratio k.
A subsequence of length three is a combination of three such indexes i1, i2, i3, that 1 ≤ i1 < i2 < i3 ≤ n. That is, a subsequence of length three are such groups of three elements that are not necessarily consecutive in the sequence, but their indexes are strictly increasing.
A geometric progression with common ratio k is a sequence of numbers of the form b·k0, b·k1, ..., b·kr - 1.
Polycarp is only three years old, so he can not calculate this number himself. Help him to do it.
Input
The first line of the input contains two integers, n and k (1 ≤ n, k ≤ 2·105), showing how many numbers Polycarp's sequence has and his favorite number.
The second line contains n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — elements of the sequence.
Output
Output a single number — the number of ways to choose a subsequence of length three, such that it forms a geometric progression with a common ratio k.
Sample Input
5 2
1 1 2 2 4
Sample Output
4
HINT
题意
找出 给定序列中 三个数 使得 成等比数列
题解：
枚举中值，map暴力就可以
代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
#include <stack>
typedef __int64 ll;
#define inf 1000000000000
using namespace std;
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
} //**************************************************************************************
map<ll ,ll >mp;
map<ll ,ll >mp2;
ll a[];
int main()
{
ll n,k;
scanf("%I64d%I64d",&n,&k);
ll sum=;
ll f1,f2;
for(int i=; i<=n; i++)
{
scanf("%I64d",&a[i]);
if(mp.count(a[i])==)
mp[a[i]]=;
else mp[a[i]]++;
}
if(mp2.count(a[n])==)
mp2[a[n]]=;
else mp2[a[n]]++;
for(int i=n-; i>; i--)
{
if(mp2.count(a[i])==)
mp2[a[i]]=;
else mp2[a[i]]++;
ll t;
if(a[i]==a[i]*k)t=mp2[a[i]*k]-;
else t=mp2[a[i]*k];
if(a[i]%k==)
sum+=((mp[a[i]/k]-mp2[a[i]/k])*(t));
}
cout<<sum<<endl;
return ;
}