内存限制：256 MiB时间限制：1000 ms输入文件：pairs.in输出文件：pairs.out
题目描述小W是一个可爱的女孩子，她很喜欢二元组。现在小W有一个质数 p p p和一个长度为 n n n的整数序列 a a a以及一个整数 k k k，而她最近爱上了一种特殊的二元组 S h m i l y P a i r \rm Shmily~Pair Shmily Pair。小W认为一个二元组 ( i , j ) (i,j) (i,j)是 S h m i l y P a i r \rm Shmily~Pair Shmily Pair，当且仅当 ( a i + a j ) ( a i 2 + a j 2 ) ≡ k m o d p (a_i+a_j)(a_i^2+a_j^2) \equiv k \mod p (ai+aj)(ai2+aj2)≡kmodp，其中 1 ⩽ i < j ⩽ n 1 \leqslant i<j \leqslant n 1⩽i<j⩽n。现在小W想要知道她拥有的整数序列 a a a中，有多少个二元组是 S h m i l y P a i r \rm Shmily~Pair Shmily Pair。 输入格式第一行三个整数 n , p , k n,p,k n,p,k。第二行 n n n个整数，描述了一个整数序列 a a a。 输出格式仅一行，一个整数，表示 S h m i l y P a i r \rm Shmily~Pair Shmily Pair的个数。 样例样例输入6 7 21 2 3 4 5 6样例输出3 数据范围与提示对于 30 % 30 \% 30%的数据， n ⩽ 1 0 4 n \leqslant 10^4 n⩽104。对于 60 % 60 \% 60%的数据， n ⩽ 3 × 1 0 5 n \leqslant 3 \times 10^5 n⩽3×105。对于 100 % 100 \% 100%的数据， 2 ⩽ n ⩽ 5 × 1 0 6 2 \leqslant n \leqslant 5 \times 10^6 2⩽n⩽5×106， 2 ⩽ p ⩽ 1 0 9 2 \leqslant p \leqslant 10^9 2⩽p⩽109， 0 ⩽ k < p 0 \leqslant k <p 0⩽k<p。 提示我们先将式子化一下： ( a i 2 − a j 2 ) ( a i 2 + a j 2 ) ≡ k ( a i − a j ) m o d p (a^2_i − a^2_j )(a^2_i + a^2_j ) \equiv k(a_i − a_j) \mod p (ai2−aj2)(ai2+aj2)≡k(ai−aj)modp a i 4 − a j 4 ≡ k a i − k a j m o d p a^4_i − a^4_j \equiv ka_i − ka_j \mod p ai4−aj4≡kai−kajmodp a i 4 − k a i ≡ a j 4 − k a j m o d p a^4_i − ka_i ≡ a^4_j − ka_j \mod p ai4−kai≡aj4−kajmodp由于 k k k确定，所以我们将 a i 4 − k a i a^4_i −ka_i ai4−kai取模后丢进 m a p map map里，然后就可以统计有多少个数和它相同了。代码
#include <fstream> #include <algorithm> #include <cmath> #include <map> std::ifstream fin("pairs.in"); std::ofstream fout("pairs.out"); int main(){ fin.sync_with_stdio(false); fout.sync_with_stdio(false); int n,p,k,ans=0; fin>>n>>p>>k; std::map<int,int> s; long long x; for(int i=0,tmp;i<n;i++){ fin>>x; tmp=(((((((((x%p)*x)%p)*x%p)*x)%p)-(k*x%p))+p)%p)%p; ans+=s[tmp]; s[tmp]++; } fout<<ans<<std::endl; return 0; }