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;
}
}