Solution for Codeforces Problem 1188B - Count Pairs

· · 题解

本文章将同步到 Hexo 博客.

题意

给定一个质数 p, 一个数列 a_1, a_2, \cdots, a_n, 与一个整数 k.
求满足 (a_i + a_j)(a_i^2 +a_j^2) \equiv k \mod p 的数对 (i, j) 的个数.

解析

这是一道数学题.

同余方程有一些性质:
若 a \equiv b \mod p, 那么可以得出:

a + c \equiv b + c \mod p a \cdot c \equiv b \cdot c \mod p

也就是说同余方程可以进行移项操作, 也可以两边同时乘一个数, 方程依然成立.

还需要了解的是平方差公式:

(a + b)(a - b) = a^2 - ab + ab - b^2 = a^2 - b^2

知道上面的东西后, 便可以对式子进行一些处理.

(a_i + a_j)(a_i^2 +a_j^2) \equiv k \mod p

两边同时乘 a_i - a_j 得

(a_i + a_j)(a_i^2 + a_j^2) \cdot (a_i - a_j) \equiv k \cdot (a_i - a_j) \mod p (a_i + a_j)(a_i - a_j) \cdot (a_i^2 + a_j^2) \equiv k a_i - k a_j \mod p

运用平方差公式进行化简

(a_i^2 - a_j^2)(a_i^2 + a_j^2) \equiv k a_i - k a_j \mod p a_i^4 - a_j^4 \equiv k a_i - k a_j \mod p a_i^4 - k a_i \equiv a_j^4 - k a_j \mod p

最后, 我们对于每一个 a_i 算出 a_i^4 - k a_i \bmod p 的值, 并且存入 map 中. 所有满足 1 \leqslant j < i 且 a_j^4 - k a_j \bmod p = a_i^4 - k a_i \bmod p (即 a_j^4 - k a_j \equiv a_i^4 - k a_i \mod p) 的 j 的个数计入到最终答案中.

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, p, k;
ll a[300001];
map<ll, ll> b;
ll cnt = 0;

template <typename T>
inline T read() {
    T x = 0;
    T multiplier = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            multiplier = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch & 15);
        ch = getchar();
    }
    return x * multiplier;
}

int main() {
    n = read<ll>(), p = read<ll>(), k = read<ll>();
    for (int i = 1; i <= n; i++) {
        a[i] = read<ll>();
        ll x = a[i] * a[i] % p * a[i] % p * a[i] % p - a[i] * k % p;
        x %= p;
        x += (x < 0 ? p : 0);
        cnt += b[x]; // 先更新答案
        b[x]++;      // 后更新 map
    }

    cout << cnt << '\n';

    return 0;
}