@bit_cracker007 >> because gcd of {a, a, c} and {a, c} is the same so why keep duplicate elements in the array, hence set is used to keep only unique elements. But again as @betlista pointed out if all Ai are really distinct then why is tester using set?
but, if the original sequence is {a, a, c}, than there are two sub sequence {a, c}, so you simply cannot keep only unique elements…
once actual gcd is 1, it cannot change to something else…
…and when you are at position pos, there are (N-pos) elements in sequence and you can use every possible subset of those (N-pos) elements. Number of subsekt for K elements is 2^K.
That meaning of the sum is “choose element at position i as first one”.
2 Likes
#include <math.h>
#include <stdio.h>
typedef long long int LL;
int arr[100];
int gcd(int a, int b)
{
if(a<b)
{
int tmp=a;
a=b;
b=tmp;
}
if(a%b==0)
return b;
int c;
while(a%b!=0)
{
c = b;
b = a%b;
a = c;
}
return b;
}
int main()
{
int t;
int n;
scanf("%d", &t);
int i,j;
int c;
int rgcd;
while(t--)
{
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &arr[i]);
}
LL ans = 0;
for(i=0; i<n; i++)
{
c = 0;
for(j=i+1; j<n; j++)
{
if(gcd(arr[i], arr[j])==1)
c++;
}
ans += ((pow(2.0, c)-1)*pow(2.0, n-i-c-1));
if(arr[i]==1)
ans++;
}
if(ans==0)
{
//if you didn't find any seq. yet.. check the whole sequence..
rgcd = arr[0];
for(i=1; i<n && rgcd!=1; i++)
rgcd = gcd(arr[i], rgcd);
if(rgcd==1)
ans++;
}
printf("%lld\n", ans);
}
return 0;
}
Can anybody tell me whats wrong with this code? I have counted all the numbers whose gcd is 1 w.r.t the current one, and all those which doesn’t have gcd as ‘1’. Then i calculated the sequences using the relation in the program…
Initially i had also used similar approach but it counts only those sequences which have at least one pair with gcd=1. It doesn’t count sub sequences such as (6,10,15) in which no pair is relatively prime.
@bit_cracker007 As a tester it is important to submit solutions that assert the bounds of the test data. The set exists to simply verify that the given numbers are unique. This way, as we keep changing the test files and rejudging our submissions we automatically verify that the the bounds of the input are met.
“All Ai will be distinct” has a very important role. It means that all sub-sequences will be unique. Otherwise, there would have been many doubts regarding whether to count only unique sub-sequences or not. The problem would have been slightly harder in that case.
3 Likes
I also had done this before.This is wrong.You Dont need to do this.The number of gcds are small(10^4),so u can use idea of subset-sum problem in here.
sry abt that… i didnt think this way… thanx alot… 
@pragrame can you please explain how you came up with this dp function. Please elaborate it.
And also put some light on the condition to make it fast that you had mentioned in the last
1 Like
I described it better in this thread - http://discuss.codechef.com/questions/10495/amsgame2-editorial?page=1#10531
Something unclear?
1 Like
@gamabunta thanks for your answer, I agree with you: “Otherwise, there would have been many doubts regarding whether to count only unique sub-sequences or not.” the problem would be slightly harder to understand, but the algorihm is correct if there are duplicities or not 
Of cource two sub-sequences are different iff element indexes from original sequence are different.
@bugkiller: That was the reason I asked why has been used when all a[i] are already distinct.
@gamabunta : Thanks for clarifying.
My approach: for each divisor, count the number of integers it divides (div[i]), then compute the numbers of sequences with GCD equal to i: A[i] == 2^(div[i])-1-sum(j from 2 to a_max)A[j*i]. The first term is the number of non-empty sequences with gcd divisible by i, the 2nd is subtracting all sequences with gcd equal to greater multiples of i.
Works in O(N*sqrt(a_max)+a_max*ln(a_max)) per test case, 0.04 s realtime.
1 Like
@bugkiller , went through your solution . nice approach used. can you elaborate the process ?
3 Likes
How curious.
It seems the addition of long in Java is unfathomably slow!
Your solution passes well within the time limits with just this little change. Do a diff to figure.
My approach :
I calculated gcd of all elements of power set of the numbers. Counted number of GCDs which were 1. Still it gave wrong answer. It was working on sample testcase. Can anyone point out what was wrong? Code is here : http://www.codechef.com/viewsolution/2170999
This may give TLE but I am more worried about the wrong answer(WA) right now.
@al3x1784 >> Actually its not my solution, its acube’s solution. See the comment on the top of the code. And you’ll understand it if you start by taking an example (2, 3); then extend it to (2, 3, 4). Comment back your progress whether you got it or not, then I will help you.
Thanx for replying btw if you have understood well then pls explain giving the link to the solution so that everybody will get benefitted.
For example, lets start with the array {2, 3}.
in the for loop, it does nothing and comes out and sets d[2] = 1, okay?
then for 3, it went into the if clause, and updates d[gcd(2,3)] = d[1] to 1. Finally we are printing d[1] which was 1. Pretty fair? Now similarly we will proceed for array {2, 3, 4}
1 Like