competitive-programming/codeforces/rounds/008-gcd-of-an-array.cpp at main · UnknownHacker1/competitive-programming · 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
/*
 * GCD of an Array  [1493D]
 * Problem:  https://codeforces.com/problemset/problem/1493/D
 * Verdict:  ACCEPTED        Solved: 2022-01-17
 * Language: C++20 (GCC 11-64)
 * Runtime:  1356 ms     Memory: 113800 KB
 * Tags:     brute force, data structures, hashing, implementation, math, number theory, sortings, two pointers
 * Author:   BidoTeima
 * Source:   https://codeforces.com/contest/1493/submission/143136562
 */

/// isA AC
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void ACPLS()
{
#ifndef ONLINE_JUDGE
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
#define tc         \
    int tttttt,subtask;    \
    cin >> tttttt /*>> subtask*/; \
    while (tttttt--)

#define sumrange(l, r, arr) (l == 0 ? arr[r] : arr[r] - arr[l - 1])
#define all(v) v.begin(), v.end()
ll mod = 1e9 + 7;
ll POW(ll a, ll b) {
    ll ans = 1;
    while (b > 0) {
        if (b & 1)ans = (ans % mod * a % mod) % mod;
        ans = (a % mod * a % mod) % mod;
        b /= 2;
    }
    return ans;
}
int main()
{
    ACPLS();
    vector<int>lp((int)2e5 + 5,0);
    for (ll i = 2; i <= 2e5 + 1; i++) {
        for (ll j = i * i; j <= 2e5 + 1; j += i) {
            if (!lp[j])
                lp[j] = i;
            else lp[j] = min((ll)lp[j], i);
        }
        if (!lp[i])lp[i] = i;
    }
    int n, q;
    cin >> n >> q;
    vector<multiset<int>>st((int)2e5 + 5);
    vector<map<int,int>>freq((int)2e5+5);
    ll ans = 1;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        while (lp[x]) {
            auto& f = freq[i][lp[x]];
            auto& s = st[lp[x]];
            int mn = (s.size() != n ? 0 : *s.begin());
            if (f != 0) {
                assert(s.size() > 0);
                s.erase(s.find(f));
            }
            ++f;
            s.insert(f);
            int newmn = (s.size() != n ? 0 : *s.begin());
            //cout<<mn<<' '<<newmn<<'\n';
            if (newmn > mn) {
                ans = (ans % mod * lp[x] % mod) % mod;
            }
            x /= lp[x];
            assert(s.size() <= n);
        }
        //cout<<'\n';
    }
    //cout<<ans<<'\n';
    while (q--) {
        int i, x;
        cin >> i >> x;
        --i;
        while (lp[x]) {
            auto& f = freq[i][lp[x]];
            auto& s = st[lp[x]];
            int mn = (s.size() != n ? 0 : *s.begin());
            if (f != 0) {
                assert(s.size() > 0);
                s.erase(s.find(f));
            }
            ++f;
            s.insert(f);
            int newmn = (s.size() != n ? 0 : *s.begin());
            //cout<<mn<<' '<<newmn<<'\n';
            if (newmn > mn) {
                ans = (ans % mod * lp[x] % mod) % mod;
            }
            x /= lp[x];
            assert(s.size() <= n);
        }
        cout << ans << '\n';
    }
}