扩展欧拉定理及其应用

扩展欧拉定理大概长这样

扩展欧拉定理

平常基本上只用到gcd(a,p)==1时的情况,然而题目越来越毒瘤,就要用扩展欧拉定理。


bzoj 3884下面贴上出题人的题解,我就不赘述了。
出题人sol

今天看见了另一道题,所以想记录一下= =
codeforces 906D也就是这道题。

题目描述

给出一个长度为n的序列,以及模数p和询问数q,每次给定询问区间[l,r],询问w_{l}^{w_{l+1}^{w_{l+2}^{{...}^{w_{r}}}}} \% p的值是多少,然后我们就可以通过扩展欧拉定理套路一下递归计算,但是有一个坑点就是指数有可能一开始就小于\varphi(p)所以需要特判一下。写起来还是蛮简单的

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注