【BZOJ1951】【SDOI2010】古代猪文

题面怎么这么鬼。。就是要求

$$G^{\sum_{d|n}C_n^d}\pmod {P}$$

其中\(P=999911659\),考虑到\(P\)是个质数

那么当\(P\ne G\)时,上式就等于\(G^{\sum_{d|n}C_n^d \pmod {P-1}}\pmod P\)

那么关键就是求\(\sum_{d|n}C_n^d \pmod {P-1}\)

由于\(P-1=2\times 3\times 4679\times 35617\)

那么分别用Lucas定理求出模这四个数的结果再用中国剩余定理合并

(然而这些定理都不记得了)

Lucas定理:\(C_{n}^{m}\equiv C_{n/P}^{m/P}C_{n\%p}^{m\%p}\pmod P\)

中国剩余定理:若

$$x\equiv a_1\pmod{p_1}$$

$$x\equiv a_2\pmod{p_2}$$

$$…$$

$$x\equiv a_m\pmod{p_m}$$

那么有

$$x\equiv \sum_{i=1}^{m}a_i\frac{n}{p_i}[(\frac{n}{p_i})^{-1}\pmod{p_i}]$$

即可。

说点什么

1 评论 在 "【BZOJ1951】【SDOI2010】古代猪文"

提醒
排序:   最新 | 最旧 | 得票最多
游客

泥又在写火题!

wpDiscuz