BZOJ 4869: [Shoi2017] 相逢是问候


题目链接: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,懒得写了。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4869: [Shoi2017] 相逢是问候


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , , ,