作业帮 > 综合 > 作业

输入n,m,k,计算sm(n)的后K位数.其中 sm(n)=1^m+2^m+…+n^m,1

来源:学生作业帮 编辑:拍题作业网作业帮 分类:综合作业 时间:2024/05/01 11:23:59
输入n,m,k,计算sm(n)的后K位数.其中 sm(n)=1^m+2^m+…+n^m,1
基本算法就是高精度加法乘法,但是要优化,否则会很慢.
1:a^m=a^(m/2)*a^(m/2),用二分法可以很快的计算高次方运算值.
2:计算时仅仅计算后k位,因为前面的数据忽略不会影响后面的值
同余方程定义:( a^m =a^k*a^(m-k) (mod s) )
3:分解质因数,仅仅计算质数即可(6^k=3^k*2^k)这个优化很重要.
程序我就不发了,我也在编程,很忙啊,只能给你想到这么多了,希望对你有帮助.