zcmimi's blog

arrow_backcrt共4篇文章

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 15:07:00
查看原题

点击跳转

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

点击跳转

avatar
zc
2020-03-07 20:32:00
查看原题

点击跳转

扩展中国剩余定理

给定方程组:

\begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \\ x\equiv a_2\ ({\rm mod}\ m_2) \\ ... \\ x \equiv a_n\ ({\rm mod}\ m_n) \end{cases}

求最小的非负整数x

假设我们求出了前i-1组的解x_{i-1}

M=\operatorname{lcm}(m_1,m_2,\cdots,m_{i-1})

x_{i-1}+\lambda M \equiv a_{i-1} \pmod{m_{i-1}}(\lambda \in \Z)

那么我们需要求出最小的非负整数t使:

x_{i-1}+tM\equiv a_i \pmod{m_i}

也就是Mt\equiv a_i-x_{i-1} \pmod{m_i}

可以使用Exgcd求解t (ax\equiv c \pmod b)

如果无解,则整个方程误解

若有解,x_i=x_{i-1}+tM

1/1
Search
search