C++编程题：我是看到你回答过这题才问你,"(n1+n2+n3+...+nk ) % 1000000007平方,3次方,4次方等.麻烦帮我计算一下结果,(0 ≤ n ≤ 10^80 < k ≤ 10^6,最好C++编程出来原题：Problem DescriptionThe problem is simple:Giv
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/28 02:13:21
C++编程题：我是看到你回答过这题才问你,"(n1+n2+n3+...+nk ) % 1000000007平方,3次方,4次方等.麻烦帮我计算一下结果,(0 ≤ n ≤ 10^80 < k ≤ 10^6,最好C++编程出来原题：Problem DescriptionThe problem is simple:Giv
C++编程题：我是看到你回答过这题才问你,
"(n1+n2+n3+...+nk ) % 1000000007平方,3次方,4次方等.麻烦帮我计算一下结果,(0 ≤ n ≤ 10^80 < k ≤ 10^6,最好C++编程出来
原题：
Problem Description
The problem is simple:Give you two integers n and k,your task is to calculate the result of "(n^1+n^2+n^3+...+n^k ) % 1000000007".
Input
There are multiple cases.Each case contains two integers n and k (0 ≤ n ≤ 10^8,0 < k ≤ 10^6).
Output
For each test case,output the answer in a single line.
Sample Input
2 2
4 3
Sample Output
6
84
C++编程题：我是看到你回答过这题才问你,"(n1+n2+n3+...+nk ) % 1000000007平方,3次方,4次方等.麻烦帮我计算一下结果,(0 ≤ n ≤ 10^80 < k ≤ 10^6,最好C++编程出来原题：Problem DescriptionThe problem is simple:Giv
.
不巧. 刚出去喝了点儿酒.代码就不给你敲了.况且我C++不太会用,
平时用C,有时为了方便也就是用用C++里面的一些库函数.
帮你看看怎么做吧,如果分析的不对你还是去百度相应的题号和题目名称,
会有更为详尽的题解的.
相应的公式我也是现查的,如果有兴趣建议你看一看数论方面的知识.
下面说说这个题吧：
（知识牵连比较大,做好心理准备.所以,如果你不理解这些,给你代码你也看不懂.）
（你先看个大概,再去看链接里的内容.）
题目中,括号里的是个等比数列结果是：n(n^k-1)/(n-1),
所以现在的问题变成了它（下面用a/b代替）对m取余.
（之前想给你详细写一下,但是太多,简单的给你罗列下大概,
不懂的你在hi我或者直接百度题解吧.）
可以知道a和b都很大,直接求a/b的值是不可能的,所以这时【乘法逆元】就有用了.
【乘法逆元】
定义：
满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元.（(a*k)%p=1）
为什么要有乘法逆元呢?
当我们要求（a/b） mod p的值,且a很大,无法直接求得a/b的值时,我们就要用到乘法逆元.我们可以通过求b关于p的乘法逆元k,将a乘上k再模p,即(a*k) mod p.其结果与(a/b) mod p等价.
引用自这里（有简单的证明）：http://blog.sina.com.cn/s/blog_7c4c33190100s48a.html
求k等同于求解求解二元不定方程：a*k=p*x+1,k和x是未知数.
而这个有用到了【扩展欧几里得】
你看看百度百科的解释吧：http://baike.baidu.com/view/1478219.htm
（这个我并没有仔细看,如果看不懂,在网上试着搜索别人关于扩展欧几里得的解释吧）
现在变成了求(a*k)%m 它等同于((a%m)*k)%m=((a%m)*(b%m))%m；
此时,解决了除b（就是除(n-1)）的问题,但是a（n(n^k-1)）对m取余怎么办?
这里用到了【快速幂取模】基于的是【快速幂】的算法思想.
去这里了http://blog.csdn.net/a363514083/article/details/6771629
至此,问题可算是解决了.
引用了很多别人的写的东西,如果看不懂,试着搜同一个关键词,参考其他人对相关知识的解释
回答的晚了些,还请见谅,呵呵~
.