夢に僕らで帆を張って
来るべき日のために夜を超え

标签 欧拉定理 下的文章

September 26, 2019

洛谷P2480/SDOI2010 古代猪文

题意:求$$G^{\sum\limits_{i=1}^N \! [i \mid N] \ C_N^i} \bmod \ 999911659$$数据范围: $1 \le G \le 1000000000,1 \le N \le 1000000000$题解:记 $P=\sum\limits_{i=1}^N\!i\!\mid\!N \ C_N^i$当 $(G,999911659)=1$ 时(因为 ...
September 26, 2019

乘法逆元

乘法逆元一、逆元的定义若 $a \cdot x \equiv 1 \ (\bmod \ p)$ 且 $(a,p)=1$ ,则称 $a$ 关于模 $p$ 的乘法逆元为 $x$ ,记为 $a^{-1}$ 。二、逆元的求法1.费马(Fermat)小定理若 $p$ 为素数,且 $(a,p)=1$ ,则有 $a^{p-1} \equiv 1 \ (\bmod \ p)$ 。由费马小定理 $$a \cd...
September 26, 2019

欧拉定理&费马小定理&扩展欧拉定理

欧拉定理 & 费马小定理一、欧拉(Euler)定理1.定理若 $(a,m)=1$ ,则$$a^{\varphi(m)} \equiv 1 \ (\bmod \ m)$$ 其中 $\varphi(m)$ 为欧拉函数,定义为小于或等于 $m$ 的正整数中与 $m$ 互质的数的数目。2.证明:记模 $m$ 意义下的缩系(小于 $m$ 且与 $m$ 互素的正整数集合)$$R=\{x_1,x_2,\d...