Question

请问这道c++题目超时怎么解决啊？？？

给你一个 n，求出 2^n 的值。答案可能会过大，最后的结果对 10007 取模。。

#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int i,sum=1;
for(i=0;i<n;i++)
{
sum=sum*2;
if(sum>10007)
{
sum=sum-10007;
}
}
cout<<sum<<endl;
return 0;
}

Answer 1

解决这个问题要考虑以下几点：
1， n >= 0时和n < 0时。
2，如果2^n的结果过大，即是一个变量保存不下时该怎么办？
3，如何快速计算出2^n，使得算法效率提高。

解答上诉问题：
1，当n < 0时，2^n为浮点数，而浮点数对%（取模运算）无效，所以不考虑。
2，当n >= 0 时，2^n即是将正整数2（其二进制表示为10)左移n位。
3，n太大时，左移超出变量能表达的最大值，这时该怎么办?
给出取模运算的性质，a ^ b % p = ((a % p)^b) % p。
那么当n太大时，可以考虑将n拆成n1 + n2。
有2^n % p = ((2^n1 % p)^n2) %p。
这样就能解决n过大的问题了。

我只能给你思路，希望你能自己写出满意的代码。

追问

那么当n太大时，可以考虑将n拆成n1 + n2。
有2^n % p = ((2^n1 % p)^n2) %p。
这个怎么拆啊？n1和n2怎么确定？还有就是你这个算法是不是和我写的算法不是同一种思路啊？

追答

你写的算法超时的原因在于。
1，你在for循环中从1遍历到了n
2，乘法运算相对移位运算来说，非常慢。

至于怎么拆分n，你可以假设用unsigned int来保存结果。
例如定义，unsigned int a = 1;
那么a的二进制位数就为 m = sizeof(unsigned int) * 8;
那么a能保存的最大整数就为 2^m - 1;
而10007需要至少14位来保存。
那么你每次能够左移的次数最多就为k = m - 1 - 14 = m - 15;
我们假设m = 32，那么每次能够左移的次数最多就为17。
这样我们就可以每次左移17次，然后模除10007 ，然后n = n - 17。
最后一直模除到n = 0; 此时a中保存的就是我们需要的答案了。

追问

这个是对的，不好意思了。。。

Answer 2

思路：一直乘上2是十分耗时的，但是用另一种方法，比方说求某个数的64次方，那么只要某个数的32次方乘以这个数的32次方就行了，说白了就是某个数的32次方自乘，这样只需计算一次，而不用乘上2三十二次这种耗时的计算。实现方法可用上递归，当然不递归也行。若57，分为28与29，28可分为14自乘，29为14乘15，这时更可以设一个数组作备忘录，即计算28的14自乘时把14次方的结果储进数组里（每计出某个次方值时都储进去），然后下次用时先看一看数组有没有存，比如29里的14乘15，因为14次的之前已经计出结果，所以直接取出，而不用再次把14分成7自乘

追问

啊，不太懂啊。。

追答

#include
using namespace std;
int a[10001];//10000数组备忘录
int func(int n){
int t;
if(n0) //在备忘录范围内且备忘录中存有数则直接返回
return a[n];
if(n%2==0){ //偶数次
t=func(n/2); //递归
t=(t*t)%10007;
}
else{ //奇数次
t=(func(n/2)*func(n/2+1))%10007; //递归
}
if(n>n;
cout<<func(n)<<endl;
return 0;
}