CF 572 1C Count Pairs

给定n个数,以及p、k,问满足\((a_i+a_j)\times(a_i^2+a_j^2)=k(mod p)\)这样的二元组有多少个。n<=3e5,p<=1e9。

试了一万种变形,发现一开始把正确的略过去了。显然解三次同余方程不靠谱。正确的搞法是两边乘\(a_i-a_j\),然后发现\(a_i^4-a_j^4=k/a_i-k/a_j\),然后枚举\(a_i\)即可。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注