CF1188B Count Pairs

【题目描述】

给定一个质数 \(p\) , 一个长度为 \(n\)n 的序列 \(a = \{ a_1，a_2，\cdots，a_n\}\)一个整数 \(k\)。

求所有数对 \((i, j)\) (\(1 \le i 、j \le n\))中满足 \((a_i + a_j) \times (a_i^2 + a_j^2 ) \equiv k (\bmod p)\)的个数。

【题解】

对于题中的柿子：

\[(a_i + a_j) \times (a_i^2 + a_j^2 ) \equiv k (\bmod p)
\]

我们可以在两边同时乘上\((a_i - a_j)\)：

\[(a_i^4 - a_j^4 ) \equiv k \times (a_i - a_j) (\bmod p)
\]

移项变换一下可得：

\[a_i^4 - k \times a_i \equiv a_j^4 - k \times a_j (\bmod p)
\]

然后答案就呼之欲出了——把每个\(a_i^4 - k \times a_i\)插入\(map\)统计即可。

\(Code：\)

#include<cstdio>

#include<map>

using namespace std;

#define ll long long

#define rg register

struct ios{

	template<typename TP>

	inline ios operator >> (TP &x)

	{

		TP f=1;x=0;rg char c=getchar();

		for(;c>'9' || c<'0';c=getchar()) if(c=='-') f=-1;

		for(;c>='0' && c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^'0');

		x*=f;

		return *this;

	}

	template<typename TP>

	inline ios operator << (TP x)

	{

		int top=0,s[66];

		if(x<0) x=-x,putchar('-');

		if(!x) putchar('0');

		while(x) s[++top]=x%10+'0',x/=10;

		while(top) putchar(s[top--]);

		return *this;

	}

	inline ios operator << (char s)

	{

		putchar(s);

		return *this;

	}

}io;

const int N=3e5+5;

int n,a,k,p,ans;

map<int,int>m;

int main()

{

	io>>n>>p>>k;

	for(rg int i=1;i<=n;++i)

	{

		io>>a;

		int temp=(1ll*a*a%p*a%p*a-1ll*k*a%p+p)%p;

		ans+=m[temp],++m[temp];

	}

	io<<ans;

    return 0;

}

巴特西

CF1188B Count Pairs

【题目描述】

【题解】

\(Code：\)

最新文章

热门文章