以下程序如果通過循環進行求和，則會找到正確的答案，但如果通過GP進行公式，則不正確。爲什麼？

下面的代碼是我的問題的解決方案：http://codeforces.com/contest/327/problem/C 以下程序如果通過循環進行求和，則會找到正確的答案，但如果通過GP進行公式，則不正確。爲什麼？

，我通過循環進行求和（因此有一個糟糕的時間複雜度）第一部分給出了正確的答案。

即使我認爲使用的公式是正確的，我使用幾何級數公式的第二部分也會返回很多測試用例的不正確答案。

我在做什麼錯？（編輯： - 問題識別解釋末。）輸出

#include<stdio.h> 
#include<string> 
#include<vector> 
#include<iostream> 
typedef long long int lli; 

using namespace std; 

lli power(lli base, lli exponent) 
{ 
    lli result=1; 
    while(exponent) 
    { 
     if(exponent & 1) 
      result=(result*base)%1000000007; 
     exponent>>=1; 
     base=(base*base)%1000000007; 
    } 
    return result%1000000007; 
} 
int main() 
{ 
    string n; 
    cin>>n; 
    lli k; 
    cin>>k; 
    vector<int> position; 
    for(int i=0;i<n.length();i++) 
     if(n[i]=='5' || n[i]=='0') 
      position.push_back(i); 
    lli m=0; 
    for(int i=0;i<position.size();i++) 
     m=(m+power(2,position[i]))%1000000007; 
    lli answer=0; 
    lli l=n.length(); 

// part1 
// the following is finding summation via loop 
    for(int i=1;i<=k;i++) 
     answer=(answer + (power(2,l*(k-i))*m)%1000000007)%1000000007; 
    cout<<answer<<endl; 

//part2 
// the following finds the sum by using gp formula (1st_term*(ratio^no_of_terms-1)/(ratio-1))  
    answer=1; 
    answer=((power(power(2,l),k) - 1)/(power(2,l)-1))%1000000007; 
    answer*=m%1000000007; 
    cout<<answer<<endl; 
    return 0; 
}

夫婦的樣本輸入和

輸入1：

輸出1：

輸入2：

輸出2：

編輯： - 我已經找到了問題。模塊劃分沒有定義。功率函數返回模K的功率，其中K = 1000000007。讓我們稱這個新值爲減少的值。我將兩個減少的值分開。因此，最終答案也比實際答案少。既然我已經確定了他的問題，我仍然不知道如何克服這個問題。

Edit2： - 將第二部分更改爲以下作品（在線找到）。我不知道爲什麼。

answer=(power(power(2,l),k) - 1); 
answer=(answer*power((power(2,l)-1),K-2))%K; 
answer=(answer*m)%K;

來源

2013-07-28 Paagalpan

有趣;感謝您提出問題併發布修復程序。僅供參考，下面是你在做什麼的解釋：

你也許可以看到你（1/X即乘法）已經通過X更換分工與乘法的x ^（K-2）。所以問題是：爲什麼K-2？

答案基本上就是fermat's little theorem這就是說當你在乘以模數K（和100000007是一個素數）時，那麼x ^（K-1）= 1.如果你用x那麼你得到x ^（K-2）= 1/x。

，我希望你可以看到這可以解釋爲什麼你的代碼工作 - 在一邊你有你的K-2，由X中的其他部門。所以提高到K-2的功率相當於K，取相反。

例如，考慮3

9/3 = 3和3％5 = 3這是我們所希望的工作模5（這是素數）除以9，但師可能是一個問題：

（9％5）/ 3 = 4/3 =？這是什麼意思模5？（這是你的bug）

所以讓我們使用K-2技巧：9 *（3 ^（5-2））= 9 *（3^3）= 9 * 27 = 243和243％5 = 3

可替代地，（9％5）*（3 ^（5-2））= 4 *（3^3）= 4 * 27 = 108和108％5 = 3

來源

2013-07-28 23:32:53

感謝您的詳細解釋。 :) – Paagalpan

在你long long int表達式，你需要確保你的字面常量也long long int（您當前使用int字面常量）。因此，例如改變：

base=(base*base)%1000000007;

到：

base=(base*base)%1000000007LL;

更妙的是，你不應該垃圾通過硬編碼常量您的代碼，而只是定義一個常數，使用，例如

const long long int K = 1000000007LL; 

.... 

base=(base*base)%K;

來源

2013-07-28 18:17:33

感謝您的信息。 :)但是，問題依然存在。這是新版本，仍然給出相同的輸出： - http://ideone.com/SNQSCH – Paagalpan

另外，如果是這個問題，我相信它應該在兩個部分給出錯誤的答案。 – Paagalpan

已經確定了問題。做了相應的編輯。 – Paagalpan

模運算符％*之前=操作

來源

2013-07-28 18:20:12 cpp

感謝您的信息。但問題依然存在。這是更新版本http://ideone.com/SNQSCH – Paagalpan

以下程序如果通過循環進行求和，則會找到正確的答案，但如果通過GP進行公式，則不正確。爲什麼？

回答

相關問題