c++ - 求大数的模逆

Question

给定一个 GP 和 (1-((n-1)/n)^r) = P/Q ，当 r 很大时如何计算这个 P/Q 分数并输出 (P*Q^(-1) )%1000000007 其中 Q^(-1) 是 Q 模 1000000007 的模逆

我可以使用模幂计算 (n-1)^r 和 n^r，然后使用费马小定理使用模逆公式打印 P*Q^(-1)，但这不正确，因为我认为 ( n^r) modular inverse 与 Q^(-1) 不同，如果我在不使用模幂的情况下计算 Q，它会在 C++ 中溢出甚至 long long。那么请指导我做错了什么？

ll modInverse(ll a, ll m) 
{  
       ll ans = power(a, m-2, m);  //for finding modular inverse
       return ans;  
} 

ll power(ll x, ll y, ll p) 
{ 
    ll res = 1;      
    x = x % p;  
    while (y > 0)             // ll is long long
    {                         //p=1000000007;
        if (y & 1)            //for calculating n^r and (n-1)^r
            res = (res*x) % p; 
        y = y>>1;
        x = (x*x) % p;   
    } 
    return res; 
} 

计算 P*Q^(-1) % 1000000007 由于溢出而给出了大值的意外答案，如果使用 mod 1000000007 限制溢出则给出错误的值。我用费马小定理计算模逆和快速幂法来评估n^r。

对于

Answer 1

我们必须找到一个值 x 使得 (Qx)%MOD = 1。这意味着 (Q%MODx%MOD)%MOD = 1。这意味着对于分母，您可以使用模幂求 Q%MOD 即 (n^r)%MOD。然后将 Q%MOD 替换为 Q'。这意味着 (Q'*x)MOD=1。所以找到 Q' 的模逆。 (MOD=1000000007)