我的幂函数有什么问题,它以 2 为底数,n 为指数并计算答案模 10^9+7?
What's wrong with my power function which takes 2 as base, n as exponent and computes answer modulo 10^9+7?
我的代码:
int power(int n)
{
int num = 1000000007;
if (n == 0)
return 1;
if (n%2 == 1)
{
int storage = power((n-1)/2);
return (2*storage*storage)%num;
}
int storage = power(n/2);
return (storage*storage)%num;
}
我已经使用 exponentiation by squaring 来提高效率,我知道有些地方不对劲,因为 n= 1000
的输出生成 495105785
而正确答案是 688423210
.
我什至尝试将 return 数据类型更改为 long long 以检查行 9
和 12
中可能发生的溢出,但答案仍然相同。任何帮助将不胜感激。
如果 int 为 32 位或更小,storage * storage
可能溢出。使用溢出安全计算。
一个替代方案可以是 (int)(storage * 1LL * storage % num)
并且对于奇数幂情况类似。
storage * storage
有时可能会溢出 int
值,例如如果存储是 2^30 那么 storage * storage
是 2^60 它将被截断为 int
以适应 2^32 但你想要 full-size 计算否则你会得到错误的余数。使用 int64_t
作为中间结果,如下面的代码所示:
#include <cstdint>
#include <iostream>
using namespace std;
int power(int n)
{
int64_t num = 1000000007;
if (n == 0)
return 1;
if (n % 2 == 1)
{
int64_t storage = power((n - 1) / 2);
return (2 * storage * storage) % num;
}
int64_t storage = power(n / 2);
return (storage * storage) % num;
}
int main() {
cout << power(1000) << endl;
return 0;
}
输入:
1000
输出:
688423210
我的代码:
int power(int n)
{
int num = 1000000007;
if (n == 0)
return 1;
if (n%2 == 1)
{
int storage = power((n-1)/2);
return (2*storage*storage)%num;
}
int storage = power(n/2);
return (storage*storage)%num;
}
我已经使用 exponentiation by squaring 来提高效率,我知道有些地方不对劲,因为 n= 1000
的输出生成 495105785
而正确答案是 688423210
.
我什至尝试将 return 数据类型更改为 long long 以检查行 9
和 12
中可能发生的溢出,但答案仍然相同。任何帮助将不胜感激。
storage * storage
可能溢出。使用溢出安全计算。
一个替代方案可以是 (int)(storage * 1LL * storage % num)
并且对于奇数幂情况类似。
storage * storage
有时可能会溢出 int
值,例如如果存储是 2^30 那么 storage * storage
是 2^60 它将被截断为 int
以适应 2^32 但你想要 full-size 计算否则你会得到错误的余数。使用 int64_t
作为中间结果,如下面的代码所示:
#include <cstdint>
#include <iostream>
using namespace std;
int power(int n)
{
int64_t num = 1000000007;
if (n == 0)
return 1;
if (n % 2 == 1)
{
int64_t storage = power((n - 1) / 2);
return (2 * storage * storage) % num;
}
int64_t storage = power(n / 2);
return (storage * storage) % num;
}
int main() {
cout << power(1000) << endl;
return 0;
}
输入:
1000
输出:
688423210