大量使用pow（）

我想解決一個問題，其中的一部分需要我來計算（2^n）％1000000007，其中n < = 10^9。但是我的下面的代碼給我輸出「0」，即使對於像n = 99這樣的輸入。大量使用pow（）

有沒有其他方法，除了有一個循環，每次輸出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; 
    } 
}

來源

2012-09-03 g4ur4v

這是問了兩天前。 http://stackoverflow.com/questions/12231366/c-c-large-number-calculation比賽？家庭作業？ –

我想這是我正在尋找的。我會更新如果這個工程。謝謝 – g4ur4v

是的是的...它的工作！感謝人們的幫助。我喜歡這個網站。 – g4ur4v

你需要一個「大民」庫，目前尚不清楚你是什麼平臺上，但是從這裏開始： http://gmplib.org/

來源

2012-09-03 20:58:56

其競賽問題，我正在解決，我不能使用這個庫。謝謝無論如何。 – g4ur4v

克里斯提出了GMP，但如果你需要這一點，並希望做C++的方式，而不是C方式，沒有不必要的複雜性，你可能只想檢查this - 它編譯時會產生很少的警告，但是非常簡單，只需要Just Works™。

來源

2012-09-03 21:13:59 Griwes

這不是我期待的，因爲這將是非常緩慢的大量

使用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

我應該指出，這個工程的原因是，如果一個和b是等價的模米（即，一％M = B％米），那麼這個等式成立的多個的一個和b（即，前述的平等意味着（A * K）％M =（B * K）％ķ m）。

來源

2012-09-03 21:35:43 Bakkot

我正在處理的問題有1秒的時間限制。感謝您的幫助，但正如我所提到的，循環n次並不是我正在尋找的解決方案，當然。 – g4ur4v

您可以將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-04 03:41:05

大量使用pow（）

回答

相關問題