fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int MOD = 1e9+7;
  7. const int N = 2e5+5;
  8.  
  9. int n, q, a[N];
  10. int spf[N];
  11.  
  12. ll pw(ll x, ll n) {
  13.     ll a = 1; x %= MOD;
  14.     for (; n; n >>= 1, x = x * x % MOD)
  15.         if (n & 1) a = a * x % MOD;
  16.     return a;
  17. }
  18.  
  19. void precompute() {
  20.     iota(spf, spf + N, 0);
  21.     for (int i = 2; i * i < N; i++)
  22.         if (spf[i] == i)
  23.             for (int j = i * i; j < N; j += i)
  24.                 if (spf[j] == j) spf[j] = i;
  25. }
  26.  
  27. using T = map<int, int>;
  28. T st[4*N];
  29.  
  30. void pull(int id) {
  31.     st[id].clear();
  32.     int lc = id << 1, rc = id << 1 | 1;
  33.     if (st[lc].size() > st[rc].size()) swap(lc, rc);
  34.     for (auto& it : st[lc]) {
  35.         auto it2 = st[rc].find(it.first);
  36.         if (it2 != st[rc].end()) {
  37.             int e = min(it.second, it2->second);
  38.             if (e > 0) st[id][it.first] = e;
  39.         }
  40.     }
  41. }
  42.  
  43. void apply(int id, int x) {
  44.     while (x > 1) {
  45.         int p = spf[x];
  46.         while (x % p == 0) {
  47.             st[id][p]++;
  48.             x /= p;
  49.         }
  50.     }
  51. }
  52.  
  53. void build(int id, int l, int r) {
  54.     if (l == r) {
  55.         apply(id, a[l]);
  56.         return;
  57.     }
  58.     int mid = (l + r) >> 1;
  59.     build(id << 1, l, mid);
  60.     build(id << 1 | 1, mid + 1, r);
  61.     pull(id);
  62. }
  63.  
  64. void update(int id, int l, int r, int p, int x) {
  65.     if (l == r) {
  66.         apply(id, x);
  67.         return;
  68.     }
  69.     int mid = (l + r) >> 1;
  70.     if (p <= mid) update(id << 1, l, mid, p, x);
  71.     else update(id << 1 | 1, mid + 1, r, p, x);
  72.     pull(id);
  73. }
  74.  
  75. void solve() {
  76.     cin >> n >> q;
  77.     for (int i = 1; i <= n; i++) cin >> a[i];
  78.     build(1, 1, n);
  79.     while (q--) {
  80.         int k, x; cin >> k >> x;
  81.         update(1, 1, n, k, x);
  82.         ll ans = 1;
  83.         for (auto& it : st[1]) ans = ans * pw(it.first, it.second) % MOD;
  84.         cout << ans << '\n';
  85.     }
  86. }
  87.  
  88. int main() {
  89.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  90.  
  91.     #define TASK "GCD"
  92.     if (fopen(TASK".INP", "r")) {
  93.         freopen(TASK".INP", "r", stdin);
  94.         freopen(TASK".OUT", "w", stdout);
  95.     }
  96.  
  97.     precompute();
  98.  
  99.     int tests = 1; // cin >> tests;
  100.     while (tests--) solve();
  101.  
  102.     #ifdef LOCAL
  103.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  104.     #endif
  105.     return 0;
  106. }
Success #stdin #stdout 0.01s 41924KB
comments (?)
stdin
copy 
4 3
1 2 12 4
4 3
1 6
2 15
stdout
copy 
1
2
6
https://ideone.com/ktmWoj
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!