Skip to content
Programmingoneonone
Programmingoneonone

LEARN EVERYTHING ABOUT PROGRAMMING

  • Home
  • CS Subjects
    • IoT ? Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

LEARN EVERYTHING ABOUT PROGRAMMING

HackerEarth GCD problem solution

YASH PAL, 31 July 2024
In this HackerEarth GCD problem solution, You are given an array of N integers. A function is defined as follows:
F(i,j) = G.C.C(Ai, Ai+1, …Aj)
You are also given Q queries of the form L R. For every query, you must answer the value:
sigma(i=L,R) sigma(j=i+1, R) F(i,j)
HackerEarth GCD problem solution

HackerEarth GCD problem solution.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MAX = 200009;
const ll MAXlogN = 19;
ll ara[MAX];

ll A[MAX];
ll Log[MAX];
ll M[MAX][MAXlogN];

vector < pair < ll , ll > > perPos[MAX];

void buildSparse(ll n){
for(ll i=1;i<=n;i++) M[i][0]=A[i];
for(ll i=2;i<=n;i++) Log[i]=Log[i-1] + !(i&(i-1));

for(ll j=1; (1<<j)<=n ;j++){
for(ll i=1; (i+ (1<<j)-1) <=n; i++)
M[i][j]=__gcd(M[i][j-1],M[i + (1<<(j-1))][j - 1]);
}
}

ll Query(ll i,ll j){
ll k=Log[j-i+1];
return __gcd(M[i][k],M[j-(1<<k)+1][k]);
}

ll anss[MAX];

ll segtree[4 * MAX], lazy[4 * MAX];

void relax(ll node, ll beg, ll ed)
{
segtree[node] += lazy[node] * (ed - beg + 1);
if(beg != ed){
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
}
lazy[node] = 0;
}

void update(ll node, ll beg, ll ed, ll i, ll j, ll val)
{
if(lazy[node]) relax(node, beg, ed);
if(beg > j || ed < i || beg > ed) return;
if(beg >= i && ed <= j){
lazy[node] += val;
relax(node, beg, ed);
return;
}

ll mid = (beg + ed) / 2;
ll lft = 2 * node;
ll rgh = lft + 1;

update(lft, beg, mid, i, j, val);
update(rgh, mid + 1, ed, i, j, val);

segtree[node] = segtree[lft] + segtree[rgh];

}

ll query(ll node, ll beg, ll ed, ll i, ll j)
{
if(lazy[node]) relax(node, beg, ed);
if(beg > j || ed < i || beg > ed) return 0;
if(beg >= i && ed <= j) return segtree[node];

ll mid = (beg + ed) / 2;
ll lft = 2 * node;
ll rgh = lft + 1;

ll p = query(lft, beg, mid, i, j);
ll q = query(rgh, mid + 1, ed, i, j);

return (p + q);
}

int main()
{
// freopen("samplein01.txt", "r", stdin);
// freopen("sampleout01.txt", "w", stdout);

ll n, m;
scanf("%lld %lld", &n, &m);

for(ll i = 1; i <= n; i++){
scanf("%lld", &ara[i]);
A[i] = ara[i];
}

for(ll i = 1; i <= m; i++){
ll L, R;
scanf("%lld %lld", &L, &R);
perPos[L].push_back({R, i});
}

buildSparse(n);

for(ll i = n; i >= 1; i--){
for(ll j = i; j <= n; ){
ll lo = j, hi = n;

ll nxt = lo;

while(lo <= hi){
ll mid = (lo + hi) / 2;
if(Query(i, mid) == Query(i, j)){
nxt = mid;
lo = mid + 1;
}
else hi = mid - 1;
}

update(1, 1, n, j, nxt, Query(i, j));
j = nxt + 1;

}

for(auto el : perPos[i]){
ll l = i;
ll r = el.first;
ll id = el.second;

anss[id] = query(1, 1, n, l, r);
}

}

for(ll i = 1; i <= m; i++) printf("%lldn", anss[i]);

return 0;
}
coding problems solutions

Post navigation

Previous post
Next post
  • Automating Image Format Conversion with Python: A Complete Guide
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes