M16B - Editorial

editorial
,
1

PROBLEM LINKS :

Practice
Contest

Author : Prince Kumar Bhagat
Tester : Jaideep Pyn
Editorialist : Yash Patni

DIFFICULTY :

SIMPLE

PREREQUISITES :

MATH, OBSERVATION

PROBLEM :

For each testcase, take 2 integers a and b as input and print the largest number d, as output, such that all the integers in the range [a, b] are divisible by d.

EXPLANATION :

The problem wants us to find the GCD of all the numbers in the range [a, b]. The naive solution would be to run a loop from 1 to a, pick each integer within this range and check whether all the numbers in the range [a, b] are divisble by this integer or not. If yes, store it in a variable max. At the end print the variable max as output.
But, this solution has a time complexity of O(a x (b - a + 1)) which will lead to a TLE due to higher constraints.
The solution can be optimized with a simple observation. The gcd between a and (a+1) will always be 1. This could be easily understood as two consecutive numbers are odd and even.
Neither of the two consecutive numbers can be divisible by the same number greater than 2 beacuse for that to happen, the difference must be greater than 2 and 2 itself cannot be a factor as one of the numbers is odd. Thus, gcd = 1.
Hence the problem can be divided into 2 cases :
Case 1 : if a = b, then gcd will be a itself.
Case 2: if a != b, then gcd will be 1 no matter the range because a and (a+1) will be present in the sequence.
if a = b :
print a
else
print ‘1’
Time complexity of the solution is O(1).

AUTHOR’S SOLUTIONS :

#include <bits/stdc++.h>
#define int long long
using namespace std;
#undef int
int main() 
{
    #define int long long
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    int T;cin >> T;
    while (T--) 
    {
	string a, b;
	cin >> a >> b;
	cout << ((a == b) ? a : "1") << "\n";
    }
    return 0;
}

TESTER’S SOLUTION

#include <bits/stdc++.h>
#define int long long

using namespace std;

#undef int
int main() 
{
    #define int long long
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    int T;cin >> T;
    while (T--) 
    {
	string a, b;
	cin >> a >> b;
	cout << ((a == b) ? a : "1") << "\n";
    }
    return 0;
}
1 Like