PROBLEM LINK:
[Practice]([TEAM07 Problem - CodeChef]
Author: Venkatesh G Dhongadi
Tester: Venkatesh G Dhongadi
Editorialist: Venkatesh G Dhongadi
DIFFICULTY:
Easy-Medium
PROBLEM:
It’s a pleasant sunny day in the hidden leaf village! The members of team 7 are chilling out at some place.
Naruto and Sasuke are playing a game. Both of them are at a height X . In each jump Naruto moves up by height A and Sasuke moves up by height B. Naruto and Sasuke want to know which is the next height which will be visited by both of them.
Meanwhile Sakura and Kakashi are spectating them and are counting the number of jumps.
Sakura is counting the number of jumps made by Sasuke (obviously) and Kakashi is counting the number of jumps made by Naruto.
PREREQUISITES:
Greatest Common Divisor and Lowest Common Multiple
Basic observations
QUICK EXPLANATION:
This question is based on the logic of GCD & LCM
EXPLANATION:
The positions which will be visited by Naruto are x+a, x+2a, …The positions which will be visited by Sasuke are x+b, x+2b, …We want the next position to be the smallest. It will happen when the difference between that position and x is multiple of both a and b. Therefore next position is x+lcm(a,b).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b){return (b==0)?a:gcd(b,a%b);}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t=1;
cin>>t;
while(t--){
ll x,a,b;
cin>>x>>a>>b;
cout<<(x+(a*b)/gcd(a,b))<<"\n";
}
return 0;
}