c++ - 如何在 C++ 中找到模乘逆

Question

#include <bits/stdc++.h>

#define mx 1000005
#define mod 1000003

using namespace std;

long long arr[mx];

int fact()
{
    arr[0]=1;
    for(int i=1; i<mx; i++)
    {
        arr[i]=((i%mod)*(arr[i-1]%mod))%mod;
    }
}

int main()
{
    int t;
    long long a,b,C,E;
    fact();
    cin>>t;
    while(t--)
    {
        cin>>a>>b;

        C=(arr[a]%mod)%mod;
        E=((arr[b])%mod)*((arr[a-b])%mod)%mod;
    }

}

在这个问题中我必须计算(C/E)%1000003。我如何使用模块化乘法逆技术来做到这一点？有没有其他方法来计算这个？

Answer 1

因为 1000003 是素数。

long long mod = 1000003;
inline long long mpow(long long b, long long ex){
    if (b==1)return 1;
    long long r = 1;
    while (ex ){
        if (ex&1)r=(r * b)%mod;
        ex = ex >> 1;
        b = (b * b)%mod;}
    return r;
}

然后做

E % mod 的倒数 = mpow(E,mod-2)

Fermats's little theorem

geekforgeeks