「ditoly 暑假模拟赛」二元组 - 哈希表

发表于 | 更新于 | 分类于 | 评论数：

求有多少个非负整数二元组 (x,y)(x, y) 满足 xy+x+y=nxy + x + y = n。

链接

FZOJ #10004

题解

易得 y=n−xx+1y = {n - x \over x + 1}。

在 n\sqrt{n} 范围内枚举 xx，判断是否存在对应的 yy，若存在，则 (x,y)(x, y) 和 (y,x)(y, x) 的是合法的状态，使用一个哈希表来判重。

PS：本机极限数据 1.8 s1.8\text{ s}，交上去 AC……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cmath>
#include <utility>
#include <algorithm>
#include <tr1/unordered_set>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

struct PairHash {
    size_t operator ()(const std::pair<int, int> &p) const {
        const size_t h1 = std::tr1::hash<int>{}(p.first);
        const size_t h2 = std::tr1::hash<int>{}(p.second);
   
        return h1 ^ (h2 << 1);
    }
};

bool isInteger(const double &x) {
    return floor(x) == x;
}

int main() {
#ifndef DBG
    freopen("pair.in", "r", stdin);
    freopen("pair.out", "w", stdout);
#endif

    int t;
    scanf("%d", &t);
    
    __gnu_pbds::gp_hash_table< std::pair<int, int>, __gnu_pbds::null_type, PairHash> S;
    while (t--) {
        S.clear();
        
        int n;
        scanf("%d", &n);

        for (int x = 0; x * x <= n; ++x) {
            double y = 1.0 * (n - x) / (x + 1);
            if (isInteger(y)) {
                S.insert(std::make_pair(x, int(y)));
                S.insert(std::make_pair(int(y), x));
            }
        }
        
        printf("%d\n", S.size());
    }
}