Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ch-hristov/6389fb6eac4c040eee818dadf2dc1baa to your computer and use it in GitHub Desktop.
Save ch-hristov/6389fb6eac4c040eee818dadf2dc1baa to your computer and use it in GitHub Desktop.
GCD
//https://www.hackerrank.com/contests/25-years-nbu/challenges/gcd-6
#include "stdafx.h"
#include <vector>
#include <algorithm>
#include <math.h>
#include <iostream>
using namespace std;
const int maxi = 10e5 + 7;
int gcd(int a, int b){
int r = a % b;
if (r == 0) return b;
else return gcd(b, a%b);
}
int getMid(int x, int y){
return x + (y - x) / 2;
}
class node {
int value;
vector<int> children;
public:
node(int v){
this->value = v;
};
};
class segmentTree {
int* st;
public:
segmentTree(int n){
//Height of segment tree
int x = (int)(ceil(log2(n)));
//Maximum size of segment tree
int max_size = 2 * (int)pow(2, x) - 1;
st = new int[max_size];
}
public:
int build(int left, int right, int* arr, int index){
if (left == right)
return arr[left];
int mid = getMid(left, right);
int value = gcd(build(left, mid, arr, index * 2),
build(mid + 1, right, arr, index * 2 + 1));
st[index] = value;
return value;
}
public:
void update(int ind, int val){
}
public:
int query(int left, int right){
return -1;
}
};
int d[maxi];
int _tmain(int argc, _TCHAR* argv[])
{
int N;
cin >> N;
int x;
for (int i = 0; i < N; i++){
cin >> d[i];
}
segmentTree* t = new segmentTree(N);
t->build(0, N - 1, d, 0);
while (cin >> x){
if (x == 3) break;
if (x == 1){
int ind, val;
cin >> ind >> val;
t->update(ind, val);
}
if (x == 2){
int l, r;
cin >> l >> r;
int ans = t->query(l, r);
cout << ans << endl;
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment