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… 
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.
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.
@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
explain this part...
for (; n--;) {
int x;
scanf("%d", &x);
for (int i = 1; i <= 10000; i++)
if (d[i])
d[__gcd(i, x)] += d[i]; //here?
d[x] += d[0]; // why this?
}
```
because, if no such d[i] was found then you know that this element was encountered previously so you update it so that elements coming in future know that particular d[i] is not zero anymore. Told you, take an example and you’ll be fine with it.
1 Like
You have to choose the first element somehow, in f(0, a[0]) you chose a[0] as GCD, but if you skip a[0] GCD is different…
counter example is
1
1
1
your code prints 0 - OF9ewE - Online C++ Compiler & Debugging Tool - Ideone.com, { 1 } is correct sub-sequence
The recursive function is calling itself recursively. 
Read this http://discuss.codechef.com/questions/10495/amsgame2-editorial?page=1#10531
@bugkiller i can get the answer by dry run of ur code but cant get the logic of the line “d[__gcd(i, x)] += d[i];” please explain
Can somebody help me understand the tester’s solution?
My solution used N * (1e4 + 1) space. Tester’s solution uses far less. I do not understand how everything is working in those nested loops.
2 Likes
Pls explain the memoization technique
Knew it!!!