欧拉定理
a b ≡ { a b m o d φ ( p ) , gcd ( a , p ) = 1 a b , gcd ( a , p ) ≠ 1 , b < φ ( p ) ( m o d p ) a b m o d φ ( p ) + φ ( p ) , gcd ( a , p ) ≠ 1 , b ≥ φ ( p ) a^{b}\equiv\left\{\begin{array}{ll} a^{b \bmod \varphi(p)}, & \operatorname{gcd}(a, p)=1 \\ a^{b}, & \operatorname{gcd}(a, p) \neq 1, b<\varphi(p) \quad(\bmod\ p) \\ a^{b \bmod \varphi(p)+\varphi(p)}, & \operatorname{gcd}(a, p) \neq 1, b \geq \varphi(p) \end{array}\right. ab≡⎩ ⎨ ⎧abmodφ(p),ab,abmodφ(p)+φ(p),gcd(a,p)=1gcd(a,p)=1,b<φ(p)(mod p)gcd(a,p)=1,b≥φ(p)
题目链接
LeetCode 372. 超级次方