Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.6 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
vector<int> LOG(N, 1);
typedef long long ll ;
const ll MOD=1e9+7;
void solve() {


    int n, m;
    cin >> n >> m;
    int grid[n][m];
    int sparse[20][n][m];
    for (int i = 0; i < n; ++i) {
        for (int j=0;j<m;j++)
        {
            cin>>grid[i][j];
            sparse[0][i][j]=grid[i][j];
        }
    }

    for (int bit = 1; bit < 20; bit++) {
        for (int i = 0; i <= n-1; ++i) {
            for (int j=0;j<=m-1;j++)
            {
                int x=sparse[bit-1][i][j];
                int y=sparse[bit-1][min(i+(1<<(bit-1)),n-1)][j];
                int z=sparse[bit-1][i][min(j+(1<<(bit-1)),m-1)];
                int t=sparse[bit-1][min(i+(1<<(bit-1)),n-1)][min(j+(1<<(bit-1)),m-1)];
                sparse[bit][i][j]=gcd(gcd(x,y),gcd(z,t));
            }
        }
    }
    long long output=1;
    int q;
    cin>>q;
    while (q--) {
        int k,x,y;
        cin>>x>>y>>k;
        x--;
        y--;
        int nx=x,ny=y;
        int r=LOG[k];
        int res1= sparse[r][nx][ny];
        x=nx+k-(1<<r);
        y=ny+k-(1<<r);
        y=min(y,m-1);
        x=min(x,n-1);
        int res2= sparse[r][nx][y];
        int res3= sparse[r][x][ny];
        int res4= sparse[r][x][y];
        output*=(ll)gcd(gcd(res1,res2),gcd(res3,res4));
        output%=MOD;
    }
    cout<<output<<'\n';
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    LOG[1]=0;
    for (int i = 2; i < N; ++i) {
        LOG[i] = 1 + LOG[i / 2];
    }
    int t;
    cin>>t;
    while(t--)
        solve();
}
Leave a Comment