text: Online Queries for GCD of array after divide operations | C ++ implementation of the approach ; Function to calculate gcd of onine queries ; stores the gcd of the initial array elements ; calculates the gcd ; performing online queries ; index is 1 based ; divide the array element ; calculates the current gcd ; print the gcd after each step ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void print_gcd_online ( int n , int m , int query [ ] [ 2 ] , int arr [ ] ) { int max_gcd = 0 ; int i = 0 ; for ( i = 0 ; i < n ; i ++ ) max_gcd = __gcd ( max_gcd , arr [ i ] ) ; for ( i = 0 ; i < m ; i ++ ) { query [ i ] [ 0 ] -- ; arr [ query [ i ] [ 0 ] ] /= query [ i ] [ 1 ] ; max_gcd = __gcd ( arr [ query [ i ] [ 0 ] ] , max_gcd ) ; cout << max_gcd << endl ; } } int main ( ) { int n = 3 ; int m = 3 ; int query [ m ] [ 2 ] ; int arr [ ] = { 36 , 24 , 72 } ; query [ 0 ] [ 0 ] = 1 ; query [ 0 ] [ 1 ] = 3 ; query [ 1 ] [ 0 ] = 3 ; query [ 1 ] [ 1 ] = 12 ; query [ 2 ] [ 0 ] = 2 ; query [ 2 ] [ 1 ] = 4 ; print_gcd_online ( n , m , query , arr ) ; return 0 ; }