快速乘法逆元（离线）

用法

离线计算 \(x = [x_1, x_2, \cdots, x_n]\) 在模 \(p\) 意义下的逆元。

#include "../header.cpp"
int A[MAXN], B[MAXN];
int P[MAXN], Q[MAXN];
int main(){
  ios :: sync_with_stdio(false);
  cin.tie(nullptr);
  int n, p, K, S = 1;
  cin >> n >> p >> K;
  P[0] = 1;
  for(int i = 1;i <= n;++ i){
    cin >> A[i];
    P[i] = 1ll * P[i - 1] * A[i] % p;
  }
  Q[n] = power(P[n], p - 2, p);
  for(int i = n;i >= 1;-- i){
    Q[i - 1] = 1ll * Q[i] * A[i] % p;
    B[i] = 1ll * Q[i] * P[i - 1] % p;
  }
  int ans = 0;
  for(int i = 1;i <= n;++ i){
    S = 1ll * S * K % p;
    ans = (ans + 1ll * S * B[i]) % p;
  }
  cout << ans << "\n";
  return 0;
}