求 Σik (i=1...n) mod m
0 < m ≤ 3 × 10^6 , n, k ≤ 10^18
首先想到只需要i只需要循环到m,后面的值可以通过前缀和算出
所以问题变为了
Σik (i=1...m) mod m
可以看出直接快速幂会超时
那么只需要找出1~m中质数的k次方,其他的数用线性筛算出值
因为1~m中大约有m/(Inm)个质数
一次快速幂所用的复杂度为log级别
所以总复杂度大约是O(m)级别的
灵活运用区间内素数的分布
强得一批
原文：http://www.cnblogs.com/NicoDafaGood/p/7569476.html