C. Geometric Progression
Time Limit: 20 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
题意
要求你从一个长度为n的序列中，选出3个数，要求l1<l2<l3，使得构成一个等比为k的等比数列，问你有多少个
题解：
开两个map维护一下，维护这个数前面的每类数有多少个，维护这个数后面的每类数有多少个
然后ans+=H[a[i]/k]*H[a[i]*k]就好了
代码
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define test freopen("test.txt","r",stdin) #define maxn 2000001 #define mod 1000000007 #define eps 1e-9 const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //************************************************************************************** map<ll,ll> H1; map<ll,ll> H2; ll a[maxn]; int main() { int n=read(); ll k=read(); for(int i=0;i<n;i++) { a[i]=read(); H2[a[i]]++; } ll ans=0; for(int i=0;i<n;i++) { H2[a[i]]--; if(a[i]%k==0) ans+=H1[a[i]/k]*H2[a[i]*k]; H1[a[i]]++; } cout<<ans<<endl; }