乘法逆元

一共四种方法。

1.扩展欧几里得O(logn)

扩展欧几里得能$O(\log n)$求解不定方程$ax+by=c$.

而$ax\equiv1\pmod p$等价于$ax+py=1$(相当于$ax$加或减$y$个$p$后变成$1$)

因为$a$与$p$互质，所以变成$ax+by=gcd(a,b)$

对于$ax+by=gcd(a,b)$这个式子就可以用扩欧求解了.

\[ ax+by=gcd(a,b)=gcd(b,a\ mod\ b)=bx+(a\ mod \ b)y\\ bx+(a\ mod \ b)y=bx+(a−⌊\frac ab⌋ b) y=ay+b (x−⌊\frac ab⌋ y) \]

这样就可以递归求解了。

void exgcd(int a,int b,int &x,int &y){
    if(!b）x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a\b*x; 
}

2.快速幂O(logn)

由费马小定理：若$p$是质数，$a$为任意整数，则$a^p \equiv a\pmod p$

两边同除$a$,得$a^{p-1} \equiv 1 \pmod p$

所以$a* a^{-1}\equiv a^{p-1}\pmod p$

$a^{-1}\equiv a^{p-2}\pmod p$

3.线性推 O(1)

\[递推边界是1^{-1}\equiv 1\pmod p\\ 设p=k* i+r,k= \lfloor \frac pi\rfloor,r=p\mod i\\ 则k* i+r\equiv0\pmod p\\ (k* i+r)* (r^{-1}* i^{-1})\equiv 0\pmod p\\ k* r^{-1}+i^{-1}\equiv 0\pmod p\\ i^{-1}\equiv -k* r^{-1}\pmod p\\ i^{-1}\equiv -\lfloor \frac pi\rfloor * (p\mod i)^{-1}\pmod p \]

4.阶乘推 O(1)

$$ 设f(i)=inv[i!]=\frac{1}{i!}\pmod p\

\therefore f(i-1)=\frac1{(i-1)!}=\frac1{i!} i=f(i) i\pmod p\

求出所有f(i)后便有：\

\frac1i=\frac1{i!} (i-1)!=f(i) (i-1)!\pmod p\

注意边界是f(n),用快速幂的方法求一下。

$$

P5431

这道题需要维护一下前缀积和后缀积。

考虑将原题种的分式通分。 $$ 设s=\prod a_i,则原式=\sum_{i=1}^n\frac{k^i\frac {s}{a_i}}{s} \ =s^{-1}\sum_{i=1}^nk^if[i-1]g[i+1] \(f，g为前缀积和后缀积) $$ 因此只需要一次求逆就行。

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=5e6+10;
int n,p,k,s,ss;
int a[N],f[N],g[N];
int kp(int x,int q){
    if(q==0)return 1;
    if(q==1)return x%p;
    if(q%2==1)return x*kp(x*x%p,q>>1)%p;
    else return kp(x*x%p,q>>1)%p;
}
void init(){
    f[0]=1;
    g[n+1]=1;
    s=1;
    for(int i=1;i<=n;++i){
        s=(s*a[i])%p;
        f[i]=(f[i-1]*a[i])%p;
    }
    for(int i=n;i>=1;--i){
        g[i]=(g[i+1]*a[i])%p;
    }
    ss=kp(s,p-2)%p;
}
int read1(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9' || ch<'0'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch<='9' && ch>='0'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void write1(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write1(x/10);
    putchar(x%10+'0');
}
signed main(){
    n=read1(),p=read1(),k=read1();
    for(int i=1;i<=n;++i)a[i]=read1();
    init();
    int ans=0,kk=1;
    for(int i=1;i<=n;++i){
        kk=(kk*k)%p;
        ans=(ans+(ss*kk%p)*(f[i-1]*g[i+1]%p))%p;
    }
    write1(ans);

    return 0;
}

~~卡常出题人都是SB~~

结论：看到所有项的积除以某一项时，可以用前缀积和后缀积优化。类似的还有P1623的优化方法。这样可以避免除法。