[JZOJ5214]【HEOI、SXOI2017】相逢是问候（口胡）

Description

Solution

指数是不能取模的，这很尴尬

但是有欧拉定理
若gcd(c,p)=1，那么cx≡cxmodφ(p)modp

因为根据欧拉定理cφ(p)≡1modp

但是此处c,p并不一定互质

有欧拉定理的扩展（为什么还有这种操作。。。。）
cx≡c(xmodφ(p))+φ(p)，当x>φ(p)

可以证明，一个数不断在外面套个φ，最多logp次就会变成1

那么对于修改操作，可以证明，对于任何一个初始的Ai，经过logp次操作，就一定会变成一个只与c有关的常数
也就是说ccccc...a[i]，经过若干层会变成与c有关而与a无关的常数

设当前是cq
同时也是c(qmodφ(p))+φ(p)

继续向上一层推
设q=cq1

但是q的模数是φ(p)
相应的
q≡c(q1modφ(φ(p)))+φ(φ(p))
叠了若干个φ，最终模数会变成1，(q1modφ(φ(...φ(p)...)))=0,φ(φ(...φ(p)...))=1

指数也会是1

再怎么操作，最终的指数都是1
所以一定是常数，并且叠的层数最多logp层

可以线段树维护每个做了几层，区间求和，若区间操作次数最少的都变成常数了，那就不用做了，否则暴力修改每个叶子节点

复杂度mlognlog2p
向上递归一个，快速幂一个。

显然会T

因为底数相同，可以预处理快速幂
具体怎么弄我也不会（好吧我太弱了。。）

Code

因为是口胡，所以没有题解！