Author: Sachin Singh
Tester: Sachin Singh
Editorialist: Sachin Singh
DIFFICULTY:
CAKEWALK, SIMPLE, EASY.
PREREQUISITES:
Math .
PROBLEM:
Given an array with N integers. We have to find the total number between 1 to K which are divisible by all array elements.
QUICK EXPLANATION:
You have to given an array with size N. First find LCM of all array elements and store LCM in variable say T. Now divide K by T. it’s gives final output.
EXPLANATION:
Now we will try to under the problem by using an examples.
Let’s consider we have to given an array of size 5 and it contains elements [2,3,4,5,6].
consider we have to given K=1000.
Now we have to find total number from 1 to 1000 which is divisible by 2,3,4,5,6.
First we will find the LCM of 2,3,4,5,6. LCM will be 60. Now divide 1000 by 60. it gives 16.
its means there are total 16 elements from 1 to 1000 which is divisible by 2,3,4,5,6.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int ans=a[0];
for(int i=1;i<n;i++)
{
ans=(((a[i]*ans))/(__gcd(a[i],ans)));
}
ans=k/ans;
cout<<ans<<endl;
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int ans=a[0];
for(int i=1;i<n;i++)
{
ans=(((a[i]*ans))/(__gcd(a[i],ans)));
}
ans=k/ans;
cout<<ans<<endl;
}
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int ans=a[0];
for(int i=1;i<n;i++)
{
ans=(((a[i]*ans))/(__gcd(a[i],ans)));
}
ans=k/ans;
cout<<ans<<endl;
}
return 0;
}