11059: 【原1059】三元组

题目

题目描述

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

Description

小X在考古时发现一个锁着的石门，他看到门上面写着一些文字，大意是：

门上有着密密麻麻的数字，每个数字ai是个正整数( \(0 \leq ai\) < 100000000) ，

你只有找出里面满足条件的三元组(即i, j, k, i!=j, j!=k,i!=k)的个数，石门才能打开。

满足的条件为ai * aj = ak (mod 100000000)

可是石门上的数字太多了，作为计算机科学家的你能帮助他计算么?

Input Format

第一行一个数n，表示有石门上有n( \(n \leq 2000\) )个数字.

后面接着n行，每行一个正整数ai(\(0 \leq ai\) < 10^8)

Output Format

输出一个数m,表示有m个三元组满足条件

Hint

数字是随机的，但是保证有三元组存在 对于60%的数据, \(n \leq 300\) 对于100%的数据, \(n \leq 2000\)

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;
}