[JZOJ5214]【HEOI、SXOI2017】相逢是问候(口胡)
Description
Solution
指数是不能取模的,这很尴尬
但是有欧拉定理
若
因为根据欧拉定理
但是此处c,p并不一定互质
有欧拉定理的扩展(为什么还有这种操作。。。。)
可以证明,一个数不断在外面套个
那么对于修改操作,可以证明,对于任何一个初始的Ai,经过
也就是说
设当前是
同时也是
继续向上一层推
设
但是
相应的
叠了若干个
指数也会是1
再怎么操作,最终的指数都是1
所以一定是常数,并且叠的层数最多
可以线段树维护每个做了几层,区间求和,若区间操作次数最少的都变成常数了,那就不用做了,否则暴力修改每个叶子节点
复杂度
向上递归一个,快速幂一个。
显然会T
因为底数相同,可以预处理快速幂
具体怎么弄我也不会(好吧我太弱了。。)
Code
因为是口胡,所以没有题解!