zcmimi's blog

arrow_back欧拉定理共3篇文章

avatar
zc
2020-03-10 22:33:00
查看原题

点击跳转

题意:

G^{\sum d|{N\choose d}}\bmod 999911659

1 \le G \le 10^9,1 \le N \le 10^9

999911659是质数,根据欧拉定理:

G^{\sum d|{N\choose d}}\bmod 999911659 = G^{\sum d|{N\choose d} \bmod 999911658}\bmod 999911659

关键求\sum d|{N\choose d} \bmod 999911658

模数太大,直接lucas取模会炸

我们可以考虑将模数分解质因数

999911658=2\times 3 \times 4679 \times 35617

可以用lucas枚举约数算出

\begin{cases} a_1=\sum d|{N\choose d} \pmod 2 \\ a_2=\sum d|{N\choose d} \pmod 3 \\ a_3=\sum d|{N\choose d} \pmod {4679} \\ a_4=\sum d|{N\choose d} \pmod {35617} \end{cases}

然后通过crt求:

\begin{cases} x \equiv a_1 \pmod 2 \\ x \equiv a_2 \pmod 3 \\ x \equiv a_3 \pmod {4679} \\ x \equiv a_4 \pmod {35617} \end{cases}

avatar
zc
2020-03-08 10:54:00
查看原题

点击跳转

K^x \equiv 1 \pmod M

求最小的非负整数x

最近刚学了bsgs,一眼看成exbsgs

exbsgs可以,但是比较麻烦

看到最后是1,我们可以想到欧拉定理:

K^{\varphi(M)} \equiv 1 \pmod M(\gcd(K,M)=1)

可以发现,答案是\varphi(M)的约数,那么枚举\varphi(M)的约数即可(可以一直尝试枚举删掉约数)

\gcd(K,M)!=1时无解

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

扩展欧拉定理

b\ge \varphi(m)时,a^b \equiv a^{(b \mod \varphi(m))+\varphi(m)} \pmod m

1/1
Search
search