c++ - 如果求和是通过循环完成，则以下程序找到正确答案，但如果通过 GP 公式完成，则不正确。为什么？

Question

以下代码是我对问题的解决方案:http://codeforces.com/contest/327/problem/C

我通过循环执行求和的第一部分(因此时间复杂度很差)给出了正确答案。

我使用几何级数公式的第二部分返回了很多测试用例的错误答案，即使我认为使用的公式是正确的。

我做错了什么？ (编辑:- 确定的问题。最后解释)

#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:

4555000 3

输出1:

2080638 2080638

输入2:

4555000 8

输出2:

907276560 529323732

编辑:- 我已经找出问题所在。模除法未定义。幂函数返回幂模 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;

Answer 1

有趣；感谢您提出问题并发布修复程序。仅供引用，这里是你在做什么的解释:

您可能会看到您已将除以 x(即乘以 1/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 为模取倒数。

例如，考虑对 5(素数)求模并将 9 除以 3。

9/3 = 3 和 3%5 = 3 这是我们想要的，但除法可能是个问题:

(9%5)/3 = 4/3 = ?模 5 是什么意思？ (这是你的错误)

所以让我们使用 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