回复 @卜卜 :
可是这个题的复杂度就是$O(nlogn)$啊，实际上是达不到这个复杂度上限的，但是由于有取模和CRT所以常数比较大，100W大概4s差不多吧。

怎么暴力就AC了勒？？？ 感觉复杂度不对呀 nlogn 100W 应该过不了啊

这个似乎欧拉定理暴力乱搞就可以啦，求组合数的时候，把phi的质因子的指数维护一下，剩下的把phi当成指数搞逆元就好了。最后快速幂之前每次指数加上个phi，防止被欧拉定理的那个gcd(n,a)==1给坑掉。（组合数均大于0，所以由欧拉定理可证明正确性）

无需鉴定，评测机虚！！！

回复 @木人 :
怪我咯

留图不留种，菊花万人捅

回复 @Sky_miner :
学弟从哪里搞到我的数论十题的- -我记得我只给过老姚，千万别看我的题面，太黑暗了

题解上:http://blog.csdn.net/qq_31725915/article/details/52200152

这文件名咋不上天呢……