题目大意
给定$G,MOD=999911659$,求:
$$
G^{\sum_{k|n}(^N_k)}
$$
解析
根据费马小定理,$a^{p-1}\equiv 1(\bmod p)$,那么我们有$a^x\equiv a^{x \bmod (p-1)}(\bmod p)$对吧。
主要是因为$MOD-1$不是一个质数,但是它可以分解质因数成$4$个质数。
那就随便$lucas$一下然后$crt$合并就可以了。
WO YE BU HUI
Update your browser to view this website correctly. Update my browser now