【题解】CF1931D Divisible Pairs

解题思路

先看到第一个条件 $a_i + a_j \equiv 0\ ({\rm mod}\ x)$，可以推出如下性质：

$$a_i \ {\rm mod} \ x + a_j \ {\rm mod} \ x \equiv 0 \ ({\rm mod} \ x)$$

这样我们就可以在范围为 $0 \sim x - 1$ 中查找满足条件的值，及对于每一个 $a_i$，符合条件的 $a_j$ 为

$$(x - (a_i \ \rm mod \ x)) \ \rm mod \ x$$

而对于条件 $a_i - a_j \equiv 0\ ({\rm mod}\ y)$，只需要让 $a_i$ 和 $a_j$ 同余即可。即：

$$a_i \equiv a_j \ (\rm mod \ y)$$

我们只需要用 map 存储每个元素的两个条件，从而达到近似为 $O(1)$ 的查询。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void solve()
{
    int res = 0;
    int n, x, y; cin >> n >> x >> y;
    
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
        
    map<PII, int> mp;	// #define PII pair<int, int>
    
    for (int i = 1; i <= n; i ++)
    {
        int dx = a[i] % x, dy = a[i] % y;
        res += mp[{(x - dx) % x, dy}];
        mp[{dx, dy}] ++;
    }
    cout << res << '\n';
}