Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- /*#pragma comment(linker, "/stack:200000000")
- */
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <set>
- #include <map>
- #include <deque>
- #include <cmath>
- #include <queue>
- #include <random>
- #include <bitset>
- #include <time.h>
- #include <string>
- #include <cstdio>
- #include <vector>
- #include <cstdlib>
- #include <iomanip>
- #include <cassert>
- #include <iostream>
- #include <algorithm>
- #include <unordered_map>
- #include <unordered_set>
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- #define endl '\n'
- #define mp make_pair
- #define pbc push_back
- #define pob pop_back()
- #define empb emplace_back
- #define sp system("pause")
- #define queuel queue<long long>
- #define all(x) (x).begin(),(x).end()
- #define matrix vector<vector<ll>>
- #define pin(p) cin >> p.first >> p.second;
- #define rev(v) reverse(v.begin(),v.end());
- #define mx(v) max_element(v.begin(), v.end());
- #define mn(v) min_element(v.begin(), v.end());
- #define sout(s, c) for(auto i : s) cout << i << c;
- #define pout(p) cout << p.first << " " << p.second;
- #define er(v, l, r) erase(v.begin() + l, v.begin() + r);
- #define vin(v) for(ll i = 0; i < v.size(); ++i) cin >> v[i];
- #define vout(v, c) for(int i = 0; i < v.size(); ++i) cout << v[i] << c;
- #define pushi(v, a) for(int i = 0; i < a.size(); ++i) v.push_back(a[i]);
- #define sin(s, n) for(int i = 0; i < n; ++i){int a; cin >> a; s.insert(a);}
- #define fastio() ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- using namespace std;
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- typedef long long ll;
- typedef long double ld;
- typedef unsigned long long ull;
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- const ll INF = 1000LL * 1000 * 1000 * 1000 * 1000 * 1000;
- const int inf = 1000 * 1000 * 1000;
- const ld PI = acos(-1.0);
- const ll mod1 = inf + 7;
- const ll mod2 = inf + 9;
- const int MAXN = 1000005;
- const ld EPS = 1e-11;
- int hp = 179;
- int gcd(int a, int b)
- {
- while (b)
- {
- a %= b;
- swap(a, b);
- }
- return a;
- }
- signed main()
- {
- fastio();
- int L = 8;
- int s = (1 << L);
- int m = s - 1;
- int n;
- //cin >> n;
- scanf("%d", &n);
- int a[(int)1e5 + 228];
- int b[(int)1e5 + 228];
- for (int i = 0; i < n; ++i)
- {
- scanf("%d", &a[i]);
- //cin>>a[i];
- }
- for (int i = 0; i < n; ++i)
- {
- b[i >>L] = __gcd(b[i >> L], a[i]);
- }
- int q;
- scanf("%d", &q);
- while (q--)
- {
- int l, r;
- scanf("%d%d", &l, &r);
- //cin >> l >> r;
- l--; r--;
- int ans = 0;
- for (int i = l; i <= r; ++i)
- {
- if ((i & m) == 0 && (i >> L) != (r >> L))
- {
- ans = __gcd(ans, b[i >>L]);
- i += m;
- }
- else
- {
- ans = __gcd(ans, a[i]);
- }
- if (ans == 1)
- {
- break;
- }
- }
- printf("%d\n",ans);
- //cout << ans << '\n';
- }
- // sp;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement