AcWing 213. 古代猪文
原题链接
简单
作者:
羽笙
,
2019-09-23 18:56:08
,
所有人可见
,
阅读 1274
原题链接
ps:感觉有些地方有些牵强,尤其倒数第二段,还望大佬指点
根据拓展欧拉定理
将 次数 转化 mod (999911659 - 1 )
求组合数时过大,需要用lucas定理
999911658 不是一个质数
将999911658分解为 2x3x4679x35617
分别根据卢卡斯定理求和
转化回来时可以直接用中国剩余定理
因为分别求时是mod所有999911658的质因子
所以求最小的x分别mod所有质因子结果都相同,x一定是原数
求出的x就是次数一波快速幂求出即可
(几个用到的数论定理都好久没写了,写起来很难受)
补于20191014:机房同志们证明了剩余定理的应用
代码
搜一下 $exlucas$
还有一点就是像这题加起来是都可以吗