Problem Link:
Author - Shahil Verma
Tester - Shubham Kushwaha
Editorialist - Shahil Verma
Difficulty :
Medium
PREREQUISITES:
GCD
Problem :
We all know the famous Harshad Mehta and his ways to scam people, We know that he is planning to scam the government again. He knows that if he crosses the Indian border, Indian government won’t be able to catch him. India’s border is defined by 4 lines x = 0, y = 0 and x = X, and y = Y. And he is at the (0, 0) (origin in a 2D plane). There are X * Y cities (blocks of unit size). Every city has a government bank, and each bank has 1 crore Rupees, which he is planning to steal (obviously)! He have to take the minimum route to his target (X, Y) the extraction point of his chopper, which is a straight line from (0, 0) to (X, Y). He will steal the money from the banks of all the cities he will visit on his way to the extraction point.
Government of India is busy in this pandemic so their officials hire you to calculate their total money that Harshad Mehta will steal!
Explanation
• The number of blocks, straight line will cover will depend on the number of horizontal and vertical lines it will cut (or touch). By observing we can say that the straight line will cut X vertical lines and Y horizontal lines (including the x = X and y = Y lines it’ll touch only) so we can say that there will be (X + Y) blocks it will go through, but there’s a problem, when the straight line cuts both the horizontal and vertical line at the same point (the corner of the rectangle formed) then it does not cover 2 blocks around it, it only covers one block. So we have to exclude these many blocks which are not covered by the line through this condition. By observing it’s clear that the total number of common points (where vertical lines and horizontal lines are cut at the same point) is the gcd of X and Y. So we only subtract their gcd and that’s the answer! • ans = X + Y – gcd(X, Y);
• The other way of thinking this is that we divide the problem into partitions → means we find the number of blocks our straight line will pass till the 1st corner point it reaches. And then we multiply that answer by the total number of partitions it has.
• That number of partition is the gcd of X and Y. Let’s call gcd(x, y) = k (in this partition there will be no point where both the vertical lines and horizontal lines are cut at the same time, only the last point does so, that is the basis of making the partition)
• Now let’s find out how many blocks the straight line will cover in the 1st partition. There will be (X / k) vertical lines and (Y / k) horizontal lines in one partition (including (X / k)th and (Y / k)th line), it only covers ((X / k) – 1) lines and ((Y / k) – 1) lines in that region, because we have to exclude the last line it only touches, and explicitly adding +1 block (the last block, we just removed)
• so these are the number of blocks (the line touches) in one partition, so we multiply the number of partitions into this expression to get the total number of blocks
• ans = k * ((X / k) – 1 + (Y / k) – 1 + 1)
• ans = k * ((X / k) + (Y / k) – 1)
• ans = X + Y – k
• ans = X + Y – gcd(X, Y)
Solution
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while (t–)
{
int x,y;
cin>>x>>y;
cout<<(x+y-__gcd(x,y));
cout<<endl;
}
return 0;
}