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

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

描述

= > 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再用中国剩余定理来解.
一下子用这么多不熟悉的定理和方法感觉这个题好厉害.
终于知道当被模的数不是质数该怎么用中国剩余定理处理了.