【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
说点什么

1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
游客

泥又在写火题!