回复 @Asm.Def :
跪万古夹心神犇，考场上看出了这题神奇的性质。
性质：每个数按照f(x)=x*x%p这样移动是有环的，且环大小的lcm值非常小，而且进入环所需次数也很小。
所以线段树上维护下按环走一周的答案就行了，不是环的部分直接暴力，按势摊还后显然正确。
时间复杂度大概是O(nlogn*C+n*logp)，C是环长的lcm，写个程序算算发现很小的，也就100以下，所以就随便跑了……

回复 @cstdio :
= =考场上都没看题怎么可能会算法呢……

回复 @Asm.Def :
Orzzzzzzzzzzzzzz给考场上会算法的跪傻

自己弱不能怪社会= =考场上调试不出就是不会做= =