I did Forgot the first two conditions !!
I wrote the code using this but it is showing wrong answer. Here’s my code. Please help.
#include
#include
using namespace std;
long long int gcd(long long int a, long long int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
int main() {
int t;
cin>>t;
while (t–)
{
long int n;
cin>>n;
long long int a[n],last,slast,op1,op2;
for (long int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
last=a[n-1];
slast=a[n-2];
long long int result = a[0];
for (long int i = 1; i < n-2; i++)
result = gcd(a[i], result);
op1=gcd(result,last)+slast;
op2=gcd(result,slast)+last;
if (op1>=op2)
cout<<op1<<endl;
else
cout<<op2<<endl;
}
return 0;
}
you need to the remove duplicates.
I did gcd using segment tree and got ac .
As there are duplicates present slast won’t be a[n-2]. Better to set duplicates to 0 before sorting.
How do you say the lower bound is x + 1
? I understand its x + 1
only when the B = {x}
, but the lower bound of the answer should be 2 right ?
Got it Sorry. You can do at least x + 1
.
Yes, got it. Thank you !
I reported this during the competition but apparently it couldn’t be taken down.
why my solution gives run time error instead of running in many test cases successfully
https://www.codechef.com/viewsolution/24964013
Help Needed
I did not understand the part :
Why adding identical elements to B does not affect it but affects C ?
Thanks in advanced
GCD(8,8,8) = 8 so adding a similar element to a set does not changes the overall GCD.
GCD(6,12,24) = 6 if we add any number of 6 (or any other element currently present in the set) the GCD won’t change.
GCD(6,6,6,6,6,12,24) = 6
so adding identical elements won’t create any difference but if you add that element to C it might create difference.
Thanks again friend
Can anyone help me out pls. Even my solution is failing for first two subcases of subtask -2
https://www.codechef.com/viewsolution/25022048a
I also tried to code this way but it didn’t work. I am not able to understand how any number below the second largest contribute so much to single handedly raise the sum of gcd(even more than the highest element !). Also I am not able to understand what is the need of removing repetitive numbers here. C = {4,4,4,4,4,4,5,5,5,5,5,6,6,6,6} and B = {16} would give same result as C = {4,5,6} and B = {16}
#include <bits/stdc++.h>
#define ll long long int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
using namespace std;//coded by abhijay mitra
ll solve(std::vector<ll> v,ll n){
sort(v.begin(), v.end());
if (v[0]==v[n-1]) return 2*v[0];
ll h=v[n-1],sh=v[n-1],i=n-1,g1=v[0],g2,g3;
do{
i--;
sh=v[i];
}while(sh==h);
for (int i = 0; v[i] <sh ; ++i)
g1=__gcd(g1,v[i]);
g2=__gcd(g1,h);g3=__gcd(g1,sh);
if(g3+h>g2+sh)
return g3+h;
else return g2+sh;
}
int main()
{
ibs;cti;
int t;cin>>t;cout<<"\n";
while(t--){
ll n;cin>>n;std::vector<ll> v(n);
for (int i = 0; i < n; ++i)
cin>>v[i];
cout<<solve(v,n)<<"\n";
}
return 0;
}
This works
#include <bits/stdc++.h>
#define ll long long int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
using namespace std;//coded by abhijay mitra
ll solve(std::vector<ll> v,ll n){
sort(v.begin(), v.end());
if (v[0]==v[n-1]) return 2*v[0];
ll h=v[n-1],sh=v[n-1],i=n-1,g1=v[0],g2,g3;
do{
i--;
sh=v[i];
}while(sh==h);
for (int i = 0; v[i] <sh ; ++i)
g1=__gcd(g1,v[i]);
g2=__gcd(g1,h);g3=__gcd(g1,sh);
if(g3+h>g2+sh)
return g3+h;
else return g2+sh;
}
int main()
{
ibs;cti;
int t;cin>>t;cout<<"\n";
while(t--){
ll n;cin>>n;std::vector<ll> v(n);
for (int i = 0; i < n; ++i)
cin>>v[i];
cout<<solve(v,n)<<"\n";
}
return 0;
}
c++ implementation. great idea though
You can read the explanation on stackoverflow. It’ll always work. It took me some times to understand why this works. I just read it and that guy explained it well