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

「bignum」ライブラリが必要です。使用しているプラ​​ットフォームは明確ではありませんが、ここから始めてください：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

2^nのチャンクに分割できます2^m。あなたは見つける必要があります： `

2^m * 2^m * ... 2^(less than m)

数は32ビットCPU用でmある必要があります。31次に、あなたの答えは次のとおりです。

chunk1 % k  * chunk2 * k ...    where k=1000000007

あなたはまだO(N)です。しかし、あなたはchunk % k 最後のものを除いてすべてが等しいという事実を利用することができ、あなたはそれを作ることができますO(1)

于 2012-09-04T03:41:05.107 に答える
0

Chrisは GMP を提案しましたが、それだけが必要で、The C Way ではなく The C++ Way を実行したい場合、そして不必要な複雑さを避けたい場合は、これをチェックしてみてください- コンパイル時に警告はほとんど生成されませんが、非常にシンプルでジャストワークス™。

于 2012-09-03T21:13:59.110 に答える