C++编程题:我是看到你回答过这题才问你,
来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/08/31 09:39:13
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
"(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++不太会用,
平时用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
至此,问题可算是解决了.
引用了很多别人的写的东西,如果看不懂,试着搜同一个关键词,参考其他人对相关知识的解释
回答的晚了些,还请见谅,呵呵~
.
不巧. 刚出去喝了点儿酒.代码就不给你敲了.况且我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
至此,问题可算是解决了.
引用了很多别人的写的东西,如果看不懂,试着搜同一个关键词,参考其他人对相关知识的解释
回答的晚了些,还请见谅,呵呵~
.
你是否看到过UFO
我看到你曾经回答过一个马克思主义法学的根本特征是:阶级斗争、阶级分析.
UFO?你看到过么?大家相信有外星人么?UFO么?我是真的很好奇的...
你好,我在百度知道上看到你曾经回答过大肠杆菌的培养问题,但我不明白你说的(见补充),希望你能解释一
如果我是你女朋友你会怎么回答我?
阅读题(那个在百度看到你回答了相关问题,但是没有回答完整,)
我是一网友,看到你也提问过有关中国未来领导精英项目CFL的问题,请问你觉得申请难吗?我英语4级水
如果你上过初二,请回答
亲,看到你回答过的问题,很详细也很清楚很明白,知道你是化学高手,求助几个问题:
看到过你的一个回答 说一个可乐瓶 可以承受15个大气压 请问你是从那里知道这个数据的?
看到你回答的焊接小工件的电焊机,不知道你有没有试过,我想做一个焊接细铁丝的小电焊机,
你看到的我是蓝色的MV是什么意思