#include <bits/stdc++.h> #include "game.h" using namespace std; constexpr int N = 2001; constexpr int MX = 12; int lg[N]; struct SparseTable { int n, m; vector<vector<long long>> dp; SparseTable(int _n) { n = _n; m = __lg(n) + 1; dp.resize(n, vector<long long>(m)); } void build(vector<long long> &a) { for (int i = 0; i < n; i++) { dp[i][0] = a[i]; } for (int j = 1; j < m; j++) { for (int i = 0; i < n; i++) { if (i + (1 << (j - 1)) < n) { dp[i][j] = __gcd(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]); } } } } long long get(int l, int r) { int x = lg[r - l + 1]; return __gcd(dp[l][x], dp[r - (1 << x) + 1][x]); } }; int n, m; vector<vector<long long>> a; vector<SparseTable> t; void init(int R, int C) { for (int i = 2; i < N; i++) { lg[i] = lg[i / 2] + 1; } n = R; m = C; a.resize(n, vector<long long>(m)); for (int i = 0; i < n; i++) { t.push_back(SparseTable(m)); } } void update(int i, int j, long long k) { a[i][j] = k; t[i].build(a[i]); } long long calculate(int p, int q, int u, int v) { long long ans = 0; for (int i = p; i <= u; i++) { ans = __gcd(ans, t[i].get(q, v)); } return ans; }