luogu P3811线性求逆元

首先扩O：T了一个点（因为上界松），83分。

#include <cstdio>

using namespace std;

int n, p;

void exgcd(int a, int p, int &b, int &x){

    if (p==){

        b=, x=;

        return;

    }

    exgcd(p, a%p, b, x);

    int tmp=b;

    b=x;

    x=tmp-a/p*x;

    return;

}

int main(){

    scanf("%d%d", &n, &p);

    int x, y;

    for (int i=; i<=n; ++i){

        exgcd(i, p, x, y);

        printf("%d\n", (x+p)%p);

    }

    return ;

}

然后费马，事实证明果然更慢，上界很紧。

#include <cstdio>

using namespace std;

int n, p;

int expower(int a, int pow, int mod){

    int ans=;

    while (pow){

        if (pow&) ans=1LL*ans*a%mod;

        a=1LL*a*a%mod;

        pow>>=;

    }

    return ans;

}

int main(){

    scanf("%d%d", &n, &p);

    for (int i=; i<=n; ++i){

        printf("%d\n", expower(i, p-, p));

    }

    return ;

}

正解：首先$1^{-1} \equiv 1 \pmod p$

我们设：$p = k\cdot i + r,~r < i,~1 < i < p$

将其放在模p意义下：$k\cdot i + r \equiv 0 \pmod p$

两边同乘i，r就会得到：

$\begin{eqnarray*} k\cdot r^{-1} + i^{-1} &\equiv& 0 &\pmod p\\ i^{-1} &\equiv& -k\cdot r^{-1} &\pmod p\\ i^{-1} &\equiv& -\left\lfloor\frac{p}{i}\right\rfloor\cdot \left(p\bmod i\right)^{-1} &\pmod p\ \end{eqnarray*}$

于是核心代码就一行:

A[i] = -(p / i) * A[p % i];

我的代码：

注意：有可能是负数

#include <cstdio>

using namespace std;

const int maxn=;

int n, p, a[maxn];

int main(){

    scanf("%d%d", &n, &p);

    a[]=;

    printf("%d\n", a[]);

    for (int i=; i<=n; ++i){

        a[i]=(1LL*-(p/i)*a[p%i])%p;

        a[i]=(a[i]+p)%p;

        printf("%d\n", a[i]);

    }

    return ;

}