0

我正在尝试解决一个问题，其中一部分需要我计算 (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;
    }
}
4

5 回答 5

2

你需要一个“big num”库，不清楚你在哪个平台上，但从这里开始：http: //gmplib.org/

于 2012-09-03T20:58:56.947 回答
2

这不是我要找的，因为这对于大量的人来说会很慢

几乎任何其他解决方案都使用 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 )。

于 2012-09-03T21:35:43.953 回答
0

Chris提出了 GMP，但如果您只需要它并且想要以 C++ 方式而不是 C 方式来做事，并且没有不必要的复杂性，您可能只想检查一下- 它在编译时生成的警告很少，但非常简单和只是作品™。

于 2012-09-03T21:13:59.110 回答
0

您可以将您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)

于 2012-09-04T03:41:05.107 回答
0

我写了这个函数。它的效率非常低，但它适用于非常大的数字。它使用我自制的算法使用类似十进制的系统将大数字存储在数组中。

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()函数中的内存使用。

- 朱比曼

于 2020-12-12T11:17:02.773 回答