Sea ~g = MCD(A0, A1, ..., An)~ el máximo común divisor de todos los elementos del arreglo. Sin perdida de generalidad, supongamos que se va a realizar un cambio al elemento ~A0~ y ahora su nuevo valor es uno de sus divisores ~d~; esta operación es equivalente a añadir al elemento ~d~ al arreglo. Ahora, sabiendo que el ~MCD(A0, A1, ..., An, d) = MCD(MCD(A0, A1, ..., An), d) = MCD(g, d)~ se llega a que el nuevo máximo común divisor de todos los elementos es igual al ~MCD(g, d)~.

Complejidad ~O(MlogN)~, el logaritmo es por el calculo del mcd.

Otra vía:

Usar un segment tree para mantener el mcd de todo el arreglo. Esta solución no era la esperada, pero con una implementación rápida del segment tree y algunos que otros trucos para optimizar, puede hacerse entrar en tiempo. Es realmente difícil separar soluciones por un logaritmo.

Complejidad ~O(Mlog^2N)~, de nuevo el logaritmo es por el calculo del mcd.

Código usando Segment Tree.

    #pragma GCC optimize("Ofast")

    #include <bits/stdc++.h>
    using namespace std;

    typedef double d;
    typedef long long int ll;
    typedef long double ld;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;

    #define INIT ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0)
    #define endl '\n'
    #define fr first
    #define sc second
    #define pb push_back
    #define eb emplace_back
    #define mp make_pair
    #define lb lower_bound
    #define ub upper_bound
    #define ins insert
    #define ers erase
    #define sz(c) ((int)(c).size())
    #define all(x) (x).begin(),(x).end()
    #define unique(x) (x).resize(unique(all(x))-(x).begin())
    #define debug(_fmt,...) fprintf(stderr,"("#__VA_ARGS__ ") = (" _fmt")\n",__VA_ARGS__)

    const d eps = 1e-12;

    inline int sign(d x) { return x < -eps ? -1 : x > eps; }
    inline int realcmp(d x, d y) { return sign(x-y); }
    template<typename T> void na(vector<T>& a, int n) {a = vector<T>(n);for(T& i: a) cin >> i;}
    template<typename T> void pv(vector<T>& a) { for(T& i: a) cout << i << ' '; cout << endl; }
    template<typename T> vector<T> shrink(vector<T>& x) { vector<T> vals = x; sort(all(vals)); unique(vals); for(T& i: x) i = ub(all(vals), i) - vals.begin(); return vals; }

    const int N = 1e5;  // limit for array size
    int n;  // array size
    int t[2 * N];

    void build() {  // build the tree
      for (int i = n - 1; i > 0; --i) t[i] = __gcd(t[i<<1], t[i<<1|1]);
    }

    void modify(int p, int value) {  // set value at position p
      for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = __gcd(t[p], t[p^1]);
    }

    int query(int l, int r) {  // sum on interval [l, r)
      int res = 0;
      for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l&1) res = __gcd(res, t[l++]);
        if (r&1) res = __gcd(res, t[--r]);
      }
      return res;
    }

    inline void read(int &x)
    {
      x=0;
      int f=1;
      char ch=getchar();
      while(ch<'0'||ch>'9')
      {
        if(ch=='-')f=-1;
        ch=getchar();
      }
      while(ch>='0'&&ch<='9')
      {
        x=x*10+ch-'0';
        ch=getchar();
      }
      x*=f;
    }

    int main()
    {
      #ifdef OJUDGE
        //freopen("in","r",stdin);
      #endif
      INIT;
      int q;
      read(n);
      read(q);
      for(int i=0;i<n;++i) read(t[n+i]);
      build();

      while(q--)
      {
        int x, v;
        read(x);
        read(v);
        --x;
        int p = t[n + x] / v;
        t[n + x] = p;
        modify(x, p);
        cout << t[1] << '\n';
      }

      return 0;
    }

    #warning you will remember this, overflow is there, though you might not see it ...