问题分析
题目大意应该比较明了,就是求无序数对$(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_ineq 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^4equiv a_ik-a_jk (mod p)\
Rightarrow a_i^4-a_ikequiv 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( "%dn", Ans );
return 0;
}
近期评论