Crowd in the College
Problem Link:- CRWDCN
Author: @aayushindwan
Tester :@anon31329220
Editorialist:@aayushindwan
Difficulty:Easy
PREREQUISITES:
Number Theory,GCD of Number
EXPLAINATION:
You have to find common occurence of 3 events in n days as no of student will be maximum at that time.
We are given time duration of occurence of each event lets say x,y,z hours.
So these all occur simultaneously first time in hours=lcm of x,y,z.
Therefore in n days or (n x 24) they will occur [(n x 24)/(lcm of x , y , z)] times.
lcm of x,y,z = lcm of ((lcm of x, y) , z)
lcm of two no x,y = (x*y)/gcd(x,y)
gcd of two no can be found using different ways:
one of which is euclid algorithm which say gcd(x,y)=gcd(y%x,x)
Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll lcm(ll a,ll b)
{
ll c=(ab);
ll d=__gcd(a,b);
ll e=c/d;
return e;
}
int main()
{
ll i,j,a,b,c,t,n;
cin>>t;
while(t–)
{
cin>>n;
j=(n24);//to convert days in hours.
cin>>a>>b>>c;//first and second and third year guys.
i=lcm(a,b);
i=lcm(i,c);//calculating lcm of all the three numbers
i=j/i;// number of overlaps in n*24 hours.
cout<<i<<endl;
}
return 0;
}