@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!!!
betlista what if we pass gcd as zero at first
and what i am trying to say is …
f(0,0)
now here if we took a[i] then there gcd will be a[i] and thats like calling f(i+1,a[i]) and if we dont take a[i] then gcd 0 will be passed which is like f(i+1,0) which will call f(i+2,a[i+1]) and f(i+2,0) respectively similarly we calculate everything
https://www.codechef.com/viewsolution/39683014
this is my solution ac:)
I took advantage of the fact that we’re not interested in the actual gcd, only whether it’s greater than one or not. So all we want to know is whether there are any primes that are common to every given subsequence.
So the first step was to reduce each number to a tuple of its prime factors; this maps both 48 and 54 to (2,3) for example. I used a preprocessing step to sieve quickly for the prime factor tuple for all numbers in range.
Then for each step in the dynamic programming of establishing subsequences, we can add the tuple under consideration as one option and its overlap with the other running tuples at their appropriate frequencies. The end result is the count of the empty tuple, which is equivalent to combinations where there is no prime that is present in every element of the combination.
memoization with similar solution, but don’t know which testcases it’s failing. Please help.
https://www.codechef.com/viewsolution/57089929
can youy tell me why m,y code give wrong answer answer,can you ncorrect it
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int solve(vector& v,vector<vector>& dp,int i,int n){
if(n==1)
return 1;
if(dp[n][i]!=-1)
return dp[n][i];
return dp[n][i]=solve(v,dp,i,n-1)+solve(v,dp,__gcd(i,v[n-1]),n-1);
}
signed main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
vectorv(n);
for(int i=0;i<n;i++)
cin>>v[i];
vector<vector> dp(61,vector(1005,-1));
int ans= solve(v,dp,0,n);
cout<<ans<<endl;
}
}