# 11059: 【原1059】三元组

### 题目描述

author: 寿鹤鸣 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1059

## Sample Input

5
1
2
3
4
6


## Sample Output

2


## FineArtz's solution

/* 三元组 */
#include <iostream>
#include <algorithm>
using namespace std;

const unsigned long long MOD = 100000000, MOD2 = 5000005;
const unsigned long long SEED = 13131313131313LL;

int h[5000005], cnt[5000005];

int Hash(int x){
unsigned long long t = 0;
while (x){
t = t * SEED + x % 10;
x /= 10;
}
return (t % MOD2);
}

int find(int x){
int hs = Hash(x);
while (h[hs] != 0){
if (h[hs] == x)
return cnt[hs];
hs = (hs + 1) % MOD2;
}
return 0;
}

int main(){
long long a[2005];
int n;
bool flag = false;
cin >> n;
for (int i = 1; i <= n; ++i){
cin >> a[i];
int hs = Hash(a[i]);
while (h[hs] != 0){
if (h[hs] == a[i]){
++cnt[hs];
flag = true;
break;
}
hs = (hs + 1) % MOD2;
}
if (!flag){
h[hs] = a[i];
cnt[hs] = 1;
}
}
sort(a + 1, a + n + 1);
int ans = 0;
long long k = 0;
for (int i = 1; i <= n - 1; ++i){
for (int j = i + 1; j <= n; ++j){
if (i != j){
k = a[i] * a[j] % MOD;
int c = find(k);
if (c != 0){
ans += 2 * c;
if (a[i] == k) ans -= 2;
if (a[j] == k) ans -= 2;
}
}
}
}
cout << ans << endl;
return 0;
}


## yyong119's solution

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main() {
int num[2001];
int n;
long long total = 0;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> num[i];
sort(num + 1, num + n + 1);
for (int i = 1; i < n; ++i)
for (int j = i + 1; j <= n; ++j) {
int temp = (long long) num[i] * num[j] % 100000000, l = 1, r = n, mid;
while (r > l) {
mid = (l + r + 1) / 2;
if (num[mid] > temp) r = mid - 1;
else l = mid;
}
if ((temp == num[l]) && (l != i) && (l != j)) ++total;
}
cout << total * 2 << endl;
return 0;
}