codeforces#572Div2 E---Count Pairs【数学】【同余】

题目：http://codeforces.com/contest/1189/problem/E

题意：给定$n$个互不相同数，一个$k$和一个质数$p$。问这$n$个数中有多少对数$(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)\equiv (a_i-a_j)k = (a_i^2-a_j^2)(a_i^2+a_j^2)\equiv (a_i-a_j)k = (a_i^4-a_j^4)\equiv a_ik-a_jk = a_i^4 - a_ik \equiv a_j^4 - a_jk$

所以对于每一个数我们只需要计算$a_i^4-a_ik\,mod\,p$，然后根据这个能取到这个值的集合大小来计算答案就行了。

 #include<cstdio>

 #include<cstdlib>

 #include<map>

 #include<set>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<stack>

 #include<queue>

 #include<iostream>

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> pr;

 int n, p, k;

 const int maxn = 3e5 + ;

 int num[maxn];

 map<int, int>mp;

 int main()

 {

     scanf("%d%d%d", &n, &p, &k);

     for(int i = ; i < n; i++){

         scanf("%d", &num[i]);

         int res = ((LL)num[i] * num[i] % p * num[i] % p - k) % p * num[i] % p;

         res = (res + p) % p;

         if(mp.find(res) != mp.end()){

             mp[res] = mp[res] + ;

         }

         else{

             mp[res] = ;

         }

     }

     map<int, int>::iterator iter;

     int ans = ;

     for(iter = mp.begin(); iter != mp.end(); iter++){

         int x = iter->second;

         //cout<<iter->first<<":"<<iter->second<<endl;

         ans += x * (x - ) / ;

     }

     printf("%d\n", ans);

     return ;

 }

巴特西

codeforces#572Div2 E---Count Pairs【数学】【同余】

最新文章

热门文章