BZOJ-1951-古代猪文-SDOI2010-费马小定理+欧拉函数+lucas定理+中国剩余定理

时间：2015-04-02 09:09:45 阅读：411 评论：0 收藏：0 [点我收藏+]

描述

= > G \sum (n i),i|n m o d P

$=>G^{\sum {{n\choose i}\text{,i|n}}} modP$

$k = \sum C i n, i | n (mod P)$ $k=\sum {C_n^i , i|n}\pmod P$
$G ? (P) \equiv 1 (mod P), ? (p) = p ? 1$ $G^{\phi(P)}\equiv1\pmod P,\quad \phi(p)=p-1$
$P' = P ? 1$ $P‘=P-1$ $= > G P' \equiv 1 (mod P)$ $=>G^{P‘}\equiv 1\pmod P$
$G k \equiv G k mod P' (mod P)$ $G^k\equiv G^{k\mod P‘}\pmod P$
如何求k?
lucas定理 $(n m) = (n mod P ' m mod P ') ? (n / P ' m / P ')$ ${n\choose m}={{n\mod P‘ \choose m\mod P‘}}*{{n/P‘\choose m/P‘}}$
P’不是素数, lucas定理不适用.
所以把P‘-1拆成2*3*4679*35617再用中国剩余定理来解.
一下子用这么多不熟悉的定理和方法感觉这个题好厉害.
终于知道当被模的数不是质数该怎么用中国剩余定理处理了.

原文：http://blog.csdn.net/qq_21110267/article/details/44817527

踩

(0)

评论一句话评论（0）

分享档案

更多>