\(\prod_{i=1}^N P_i\) を \(R\) とします。クエリ \((X,V)\) に対して、もし \(P_X \neq 0 \bmod M\) ならば、答えは \(R\frac{V}{P_X}\) です。
しかし \(P_X = 0\bmod M\) のときは 0 除算になるので困ってしまいます。どうにかして回避しましょう。

\(P_i\) のうち、\(P_i =0 \bmod M\) であるものの個数を \(C\) とし、\(P_i\neq 0 \bmod M\) であるような \(P_i\) の総積を \(R'\) とします。このとき、クエリ \((X,V)\) に対する答えは以下のようになります。

• \(P_X=0\bmod M\) のとき
  • \(C>1\) なら、\(P_X\) 以外にも \(M\) の倍数が存在するので、答えは \(0\)
  • \(C=1\) なら、\(R=R'P_X\) なので、答えは \(R'V\)
• \(P_X\neq 0 \bmod M\) のとき
  • \(C>0\) なら、\(P_X\) 以外に \(M\) の倍数が存在するので、答えは \(0\)
  • \(C=0\) なら、\(R=R'\) なので、答えは \(R'\frac{V}{P_X}\)

よって \(R',C\) を予め求めておくことで、\(O(1)\) 回の四則演算でクエリに答えることができます。

素数 mod における除算は \(O(\log M)\) で行うことができるので、 \(O(N+Q\log M)\) でこの問題を解くことができます。実装の工夫により \((N+\log M+Q)\) で解くこともできます。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint = atcoder::modint;

int main(){
  int n, q, m;
  cin >> n >> q >> m;
  vector<int> p(n);
  for(int i=0; i<n; i++) cin >> p[i];

  mint::set_mod(m);
  int zero = 0;
  mint prod = 1;
  for(int i=0; i<n; i++){
    if(p[i] % m == 0){
      zero++;
    }else{
      prod = prod * p[i];
    }
  }

  for(int i=0; i<q; i++){
    int x, v;
    cin >> x >> v;
    x--;
    if(p[x] % m == 0){
      if(zero == 1){
        cout << (prod * v).val() << endl;
      }else{
        cout << 0 << endl;
      }
    }else{
      if(zero > 0){
        cout << 0 << endl;
      }else{
        cout << (prod / p[x] * v).val() << endl;
      }
    }
  }
}

実装例 (Python)

N, Q, M = map(int, input().split())
P = list(map(int, input().split()))

zero = 0
prod = 1
for p in P:
  if p % M == 0:
    zero += 1
  else:
    prod = prod * p % M

for _ in range(Q):
  x, v = map(int, input().split())
  x -= 1
  if P[x] % M == 0:
    if zero == 1:
      print(prod * v % M)
    else:
      print(0)
  else:
    if zero > 0:
      print(0)
    else:
      print(prod * pow(P[x], -1 ,M) * v % M)