75C. Modified GCD - Codeforces Solution C++

➤  Problem Link : 75C. Modified GCD 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll gcd(ll a, ll b)
{	
  if(b==0)		
  return a;	
  return gcd(b,a%b);
}

int main()
{	
  ll a,b,n;	
  cin>>a>>b;	
  ll g = gcd(a,b);	
  vector<ll> arr;	
  for(ll i=1;i*i<=g;i++)	
  {		
    if(g % i == 0)		
    {			
      arr.push_back(i);			
      arr.push_back(g/i);					
    }	
  }	
  sort(arr.begin(),arr.end());	
  cin>>n;	ll low,high;	
  while(n--)	
  {		
    cin>>low>>high;		
    auto it = upper_bound(arr.begin(),arr.end(),high);		
    if(it==arr.begin())		
    {			
      cout<<"-1\n";			
      continue;		
    }
    		
    it--;	

    if( *it >= low )			
      cout<<*it<<endl;		
    else			
      cout<<"-1\n";			
  }
}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.