Faster algorithm to find how many numbers are not divisible by a given set of numbers

Question

I am trying to solve an online judge problem: http://opc.iarcs.org.in/index.php/problems/LEAFEAT

The problem in short:

If we are given an integer L and a set of N integers s1,s2,s3..sN, we have to find how many numbers there are from 0 to L-1 which are not divisible by any of the 'si's.

For example, if we are given, L = 20 and S = {3,2,5} then there are 6 numbers from 0 to 19 which are not divisible by 3,2 or 5.

L <= 1000000000 and N <= 20.

I used the Inclusion-Exclusion principle to solve this problem:

/*Let 'T' be the number of integers that are divisible by any of the 'si's in the 
given range*/

for i in range 1 to N
  for all subsets A of length i
    if i is odd then:
      T += 1 + (L-1)/lcm(all the elements of A)
    else
      T -= 1 + (L-1)/lcm(all the elements of A)
return T

Here is my code to solve this problem

#include <stdio.h>

int N;
long long int L;
int C[30];

typedef struct{int i, key;}subset_e;
subset_e A[30];
int k;

int gcd(a,b){
int t;
    while(b != 0){
            t = a%b;
            a = b;
            b = t;
    }

    return a;
}

long long int lcm(int a, int b){
    return (a*b)/gcd(a,b);
}

long long int getlcm(int n){
  if(n == 1){
    return A[0].key;
  }
  int  i;
  long long int rlcm = lcm(A[0].key,A[1].key);
  for(i = 2;i < n; i++){
    rlcm = lcm(rlcm,A[i].key);
  }
  return rlcm;
}

int next_subset(int n){
  if(k == n-1 && A[k].i == N-1){
    if(k == 0){
      return 0;
    }
    k--;
  }
  while(k < n-1 && A[k].i == A[k+1].i-1){
    if(k <= 0){
      return 0;
    }
    k--;
  }
  A[k].key = C[A[k].i+1];
  A[k].i++;
  return 1;
}

int main(){
  int i,j,add;
  long long int sum = 0,g,temp;
  scanf("%lld%d",&L,&N);
  for(i = 0;i < N; i++){
    scanf("%d",&C[i]);
  }
  for(i = 1; i <= N; i++){
    add = i%2;
    for(j = 0;j < i; j++){
      A[j].key = C[j];
      A[j].i = j;
    }
    temp = getlcm(i);
    g = 1 + (L-1)/temp;
    if(add){
      sum += g;
    } else {
      sum -= g;
    }
    k = i-1;
    while(next_subset(i)){
      temp = getlcm(i);
      g = 1 + (L-1)/temp;
      if(add){
        sum += g;
      } else {
        sum -= g;
      }
    }
  }
  printf("%lld",L-sum);
  return 0;
}

The next_subset(n) generates the next subset of size n in the array A, if there is no subset it returns 0 otherwise it returns 1. It is based on the algorithm described by the accepted answer in this stackoverflow question.

The lcm(a,b) function returns the lcm of a and b. The get_lcm(n) function returns the lcm of all the elements in A. It uses the property : LCM(a,b,c) = LCM(LCM(a,b),c)

When I submit the problem on the judge it gives my a 'Time Limit Exceeded'. If we solve this using brute force we get only 50% of the marks.

As there can be upto 2^20 subsets my algorithm might be slow, hence I need a better algorithm to solve this problem.

EDIT:

After editing my code and changing the function to the Euclidean algorithm, I am getting a wrong answer, but my code runs within the time limit. It gives me a correct answer to the example test but not to any other test cases; here is a link to ideone where I ran my code, the first output is correct but the second is not.

Is my approach to this problem correct? If it is then I have made a mistake in my code, and I'll find it; otherwise can anyone please explain what is wrong?

Answer 1

You could also try changing your lcm function to use the Euclidean algorithm.

int gcd(int a, int b) {
    int t;

    while (b != 0) {
        t = b;
        b = a % t;
        a = t;
    }

    return a;
}

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

At least with Python, the speed differences between the two are pretty large:

>>> %timeit lcm1(103, 2013)
100000 loops, best of 3: 9.21 us per loop
>>> %timeit lcm2(103, 2013)
1000000 loops, best of 3: 1.02 us per loop