1 / 4
Mar 2021

Hey everyone, so initially I thought it may be an issue of int/ll boundaries so I changed all to ll just to be safe and see if that would solve the issue, but got stuck at the same point i.e. at around the 20/21st test. If you could please point out what I must be missing, I’d appreciate that.

Thanks in advance :slight_smile:


#include

#define ll long long
using namespace std;

int main()
{
ll N,K;
cin>>N>>K;

ll set [K]; //set of K elements

int i=0;
while(i<K){
    cin>>set [i];i++;
}

/*
now we'll create a program to determine how many elements in a set of 
integers from 1 to n inclusive are not divisible by any of the elements of 
the set 'set'. 
*/

ll subsets = (1<<K)-1; //number of subsets of the numbers we'll use as divisors
ll dem=1ll,ans=0; //defining the dem as just ll dem = 1 may cause issues, better use ll dem = 1ll
//i'm guessing even if declared as ll, 1 is still stored as int, so 1ll is necessary
for (ll i=1;i<=subsets;i++){
    ll setBits = __builtin_popcount(i); //count number of 1s in the ith subset (this tells you what set is included in the subset)
    for (ll k=0;k<K;k++)
        if (i & (1<<k)) dem*=set[k];
    if (setBits%2==0)  ans-=N/dem;
    else ans+=N/dem;
}

cout<<N-ans;

return 0;

}

  • created

    Feb '21
  • last reply

    Mar '21
  • 3

    replies

  • 649

    views

  • 2

    users

First of all SPOJ doesn’t work like that. It doesn’t stop on the first failure, so the code could be failing all test cases as far as you know.

Try this

30 5
2 17 19 21 23

Would you expect this test cases to give the same answer as above?

30 5
17 19 21 23 2

Hey Simes, thank you very much for that. I went through the code and noticed I wasn’t setting the denominator “dem” back to 1 for every subset, and fixed that. As a result, both the above test cases were giving the same answer, 11, as they should.

Still getting wrong answer and I still can’t see where the issue is. Any ideas?

Yes, retest it with the sample input given in the problem.