我正在尝试解决一个问题，其中一部分需要我计算 (2^n)%1000000007 ，其中 n<=10^9。但是我的以下代码即使对于像 n = 99 这样的输入也会给我输出“0”。
除了有一个循环每次将输出乘以 2 并且每次都找到模数之外还有其他方法吗（这不是我要寻找的，因为这对于大量数字来说会非常慢）。
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int main()
{
unsigned long long gaps,total;
while(1)
{
cin>>gaps;
total=(unsigned long long)powf(2,gaps)%1000000007;
cout<<total<<endl;
}
}
你需要一个“big num”库，不清楚你在哪个平台上，但从这里开始：http: //gmplib.org/
这不是我要找的，因为这对于大量的人来说会很慢
几乎任何其他解决方案都使用 bigint 库要慢得多。
不要在每次循环中都取模：而是只在输出增长大于模数时取模，如下所示：
#include <iostream>
int main() {
int modulus = 1000000007;
int n = 88888888;
long res = 1;
for(long i=0; i < n; ++i) {
res *= 2;
if(res > modulus)
res %= modulus;
}
std::cout << res << std::endl;
}
这实际上非常快：
$ time ./t
./t 1.19s user 0.00s system 99% cpu 1.197 total
我应该提到，这样做的原因是，如果a和b是等价的 mod m（即a % m = b % m），那么这个等式包含a和b的多个k（也就是说，上述等式意味着( a*k)%m = (b*k)%m )。
Chris提出了 GMP，但如果您只需要它并且想要以 C++ 方式而不是 C 方式来做事，并且没有不必要的复杂性，您可能只想检查一下- 它在编译时生成的警告很少，但非常简单和只是作品™。
您可以将您2^n的2^m. 你需要找到：`
2^m * 2^m * ... 2^(less than m)
数字m应该31是 32 位 CPU。那么你的答案是：
chunk1 % k * chunk2 * k ... where k=1000000007
你还在O(N)。chunk % k 但是，您可以利用除最后一个之外所有人都平等的事实，您可以做到O(1)
我写了这个函数。它的效率非常低，但它适用于非常大的数字。它使用我自制的算法使用类似十进制的系统将大数字存储在数组中。
mpfr2.cpp
#include "mpfr2.h"
void mpfr2::mpfr::setNumber(std::string a) {
for (int i = a.length() - 1, j = 0; i >= 0; ++j, --i) {
_a[j] = a[i] - '0';
}
res_size = a.length();
}
int mpfr2::mpfr::multiply(mpfr& a, mpfr b)
{
mpfr ans = mpfr();
// One by one multiply n with individual digits of res[]
int i = 0;
for (i = 0; i < b.res_size; ++i)
{
for (int j = 0; j < a.res_size; ++j) {
ans._a[i + j] += b._a[i] * a._a[j];
}
}
for (i = 0; i < a.res_size + b.res_size; i++)
{
int tmp = ans._a[i] / 10;
ans._a[i] = ans._a[i] % 10;
ans._a[i + 1] = ans._a[i + 1] + tmp;
}
for (i = a.res_size + b.res_size; i >= 0; i--)
{
if (ans._a[i] > 0) break;
}
ans.res_size = i+1;
a = ans;
return a.res_size;
}
mpfr2::mpfr mpfr2::mpfr::pow(mpfr a, mpfr b) {
mpfr t = a;
std::string bStr = "";
for (int i = b.res_size - 1; i >= 0; --i) {
bStr += std::to_string(b._a[i]);
}
int i = 1;
while (!0) {
if (bStr == std::to_string(i)) break;
a.res_size = multiply(a, t);
// Debugging
std::cout << "\npow() iteration " << i << std::endl;
++i;
}
return a;
}
mpfr2.h
#pragma once
//#infdef MPFR2_H
//#define MPFR2_H
// C standard includes
#include <iostream>
#include <string>
#define MAX 0x7fffffff/32/4 // 2147483647
namespace mpfr2 {
class mpfr
{
public:
int _a[MAX];
int res_size;
void setNumber(std::string);
static int multiply(mpfr&, mpfr);
static mpfr pow(mpfr, mpfr);
};
}
//#endif
主文件
#include <iostream>
#include <fstream>
// Local headers
#include "mpfr2.h" // Defines local mpfr algorithm library
// Namespaces
namespace m = mpfr2; // Reduce the typing a bit later...
m::mpfr tetration(m::mpfr, int);
int main() {
// Hardcoded tests
int x = 7;
std::ofstream f("out.txt");
m::mpfr t;
for(int b=1; b<x;b++) {
std::cout << "2^^" << b << std::endl; // Hardcoded message
t.setNumber("2");
m::mpfr res = tetration(t, b);
for (int i = res.res_size - 1; i >= 0; i--) {
std::cout << res._a[i];
f << res._a[i];
}
f << std::endl << std::endl;
std::cout << std::endl << std::endl;
}
char c; std::cin.ignore(); std::cin >> c;
return 0;
}
m::mpfr tetration(m::mpfr a, int b)
{
m::mpfr tmp = a;
if (b <= 0) return m::mpfr();
for (; b > 1; b--) tmp = m::mpfr::pow(a, tmp);
return tmp;
}
我为 tetration 和最终的超操作创建了这个。当数字变得非常大时，计算可能需要很长时间和大量内存。是#define MAX 0x7fffffff/32/4一个数字可以有的小数位数。稍后我可能会制作另一种算法，将这些数组中的多个组合成一个数字。在我的系统上，最大数组长度是 0x7fffffff aka 2147486347 aka 2^31-1 aka int32_max （通常是标准 int 大小）所以我必须将 int32_max 除以 32 才能创建这个数组。我还将它除以 4 以减少multiply()函数中的内存使用。
- 朱比曼