Competitive-Programming-Learning-/GCD_Queries.cpp at main · ShardenduMishra22/Competitive-Programming-Learning- · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
// #include <bits/stdc++.h>
// using namespace std;

// #pragma GCC target   ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("-ffloat-store")
// #pragma GCC optimize ("Ofast")

// static auto _ = [] () {
//     ios_base::sync_with_stdio(false);
//     cin.tie(nullptr);
//     cout.tie(nullptr);
//     return 0;
// }();

// #define frw(i, len) for(int i=0; i < len ; i++)
// #define frb(i, len) for(int i=len; i >= 0; i--)

// #define YES cout<<"Yes \n";
// #define NOO cout<<"No  \n";
// #define nl cout<<"\n";

// #define MAX_SIZE 10000
// #define nptr nullptr

// typedef stringstream strgm;
// typedef long long int ll;
// typedef const int c_int;
// typedef unsigned unsg;
// typedef double dbl;

// typedef vector<vector<string>> vvstr;
// typedef vector<vector<bool>> vvbl;
// typedef vector<vector<int>> vvint;
// typedef vector<vector<ll>> vvll;

// typedef vector<string> vstr;
// typedef vector<int> vint;
// typedef vector<bool> vbl;
// typedef vector<ll> vll;

// typedef stack<string> sstr;
// typedef stack<bool> sbl;
// typedef stack<int> sint;
// typedef stack<ll> sll;

// typedef queue<string> qstr;
// typedef queue<bool> qbl;
// typedef queue<int> qint;
// typedef queue<ll> qll;

// c_int MOD=1e9 + 7;
// c_int Mx_row=100;
// c_int Mx_col=100;
// int size_stack=0;
// int InvrsnCnt=0;
// int size_arr=0;
// int size_ll=0;
// int top=-1;


// int main() {

//     int t;
//     cin >> t;

//     while(t--) {
//         int n, q;
//         cin >> n >> q;
//         int arr[n + 1];
//         for(int i = 1; i <= n; i++) {
//             cin >> arr[i];
//         }
//         while(q--) {
//             int l, r;
//             cin >> l >> r;
//             int gc = 0;
//             for(int i = 1; i <= n; i++) {
//                 if(i < l || i > r) {
//                     gc = __gcd(gc, arr[i]);
//                 }
//             }
//             cout << gc << "\n";
//         }
//     }

//     return 0;
// }

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        int n, q;
        cin >> n >> q;

        int arr[n + 1];
        for(int i = 1; i <= n; i++) {
            cin >> arr[i];
        }

        int gcd_forward[n + 1];
        gcd_forward[0] = 0;

        for(int i = 1; i <= n; i++) {
            gcd_forward[i] = __gcd(gcd_forward[i - 1], arr[i]);
        }

        int gcd_backward[n + 2];
        gcd_backward[n + 1] = 0;

        for(int i = n; i >= 1; i--) {
            gcd_backward[i] = __gcd(gcd_backward[i + 1], arr[i]);
        }

        while(q--) {
            int l, r;
            cin >> l >> r;
            int gc = __gcd(gcd_forward[l - 1], gcd_backward[r + 1]);

            cout << gc << "\n";
        }
    }

    return 0;
}