Untitled
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