BZOJ 4869: [Shoi2017] 相逢是问候

发布于 2018-01-11  350 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4869

题意:区间求和,区间赋值为某常数的单点和幂。


\(c^a=c^{a\ mod\ \varphi(p) + \varphi(p)}\)

\(c^{c^a}=c^{c^{a \ mod \ \varphi(\varphi(p))+\varphi(\varphi(p)) }\ mod \ \varphi(p)+\varphi(p)}\)

这样一直下去,\(O(log_p)\) 次后就是不动点了。

线段树大力维护这个过程,这是三个 log 的,总时限可过(逃

靠谱一点的话可以优化掉快速幂的 log,懒得写了。

 


一个非常弱的准退役OIER