CF1188B Count Pairs

题目链接

问题分析

题目大意应该比较明了，就是求无序数对$(i,j)$满足$(a_i+a_j)(a_i^2+a_j^2)\equiv k\,\,(\mod p)$的数量。
$$
(a_i+a_j)(a_i^2+a_j^2)\equiv k\,\,(\mod p)\\
\because a_i\neq a_j \wedge a_i,a_j<p \\
\therefore (a_i-a_j)^{-1} (\mod p) \,\,\, exists\\
\therefore (a_i-a_j)(a_i+a_j)(a_i^2+a_j^2)\equiv (a_i-a_j)k (\mod p)\\
\Rightarrow a_i^4-a_j^4\equiv a_ik-a_jk (\mod p)\\
\Rightarrow a_i^4-a_ik\equiv a_j^4-a_jk (\mod p )
$$
所以做法就显然了。

当然还可以解$3$次方程。然而我并不会，所以就不介绍了

参考程序

#include <bits/stdc++.h>
using namespace std;

map< int, int > Map;

int main() {
    int n, p, k; scanf( "%d%d%d", &n, &p, &k );
    int Ans = 0;
    for( int i = 1; i <= n; ++i ) {
        int x; scanf( "%d", &x );
        x = ( 1LL * x * x % p * x % p * x % p - 1LL * x * k % p + p ) % p;
        if( Map.find( x ) != Map.end() ) Ans += Map[ x ], ++Map[ x ];
        else Map[ x ] = 1;
    }
    printf( "%d\n", Ans );
    return 0;
}