牛客Steins；Gate（原根+FFT）

2023大厂真题提交网址(含题解):

www.CodeFun2000.com（http://101.43.147.120/）

最近我们一直在将收集到的机试真题制作数据并搬运到自己的OJ上，供大家免费练习,体会真题难度。现在OJ已录入50+道2023年最新大厂真题，同时在不断的更新。同时，可以关注”塔子哥学算法”公众号获得每道题的题解。

题目大意：

给一个长度为$n$的序列。对每一个$a_k$,询问有多少个二元组$(i,j)$满足$a_i\ast a_j(modp)=a_k$.

题目思路：

这里用到了一个定理,所有素数一定存在原根。那么对于$p$的原根$g$来讲.任意一个$x\in [0,p-1]$.都存在唯一一个$i$使得$g^i=x$.所以上式可以换成：$g^i\ast g^j=g^{i+j}=g^k$,这样就将乘法变成加法了。对$g$构造多项式$A^2(x)$即为答案.FFT求一下即可.

今天的文章牛客Steins；Gate（原根+FFT）分享到此就结束了，感谢您的阅读。