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

Question 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

Question 2

Typically, the lowest common multiple of a subset of k of the s_i will exceed L for k much smaller than 20. So you need to stop early.

Probably, just inserting

if (temp >= L) {
    break;
}

after

while(next_subset(i)){
  temp = getlcm(i);

will be sufficient.

Also, shortcut if there are any 1s among the s_i, all numbers are divisible by 1.

I think the following will be faster:

unsigned gcd(unsigned a, unsigned b) {
    unsigned r;
    while(b) {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

unsigned recur(unsigned *arr, unsigned len, unsigned idx, unsigned cumul, unsigned bound) {
    if (idx >= len || bound == 0) {
        return bound;
    }
    unsigned i, g, s = arr[idx], result;
    g = s/gcd(cumul,s);
    result = bound/g;
    for(i = idx+1; i < len; ++i) {
        result -= recur(arr, len, i, cumul*g, bound/g);
    }
    return result;
}

unsigned inex(unsigned *arr, unsigned len, unsigned bound) {
    unsigned i, result = bound, t;
    for(i = 0; i < len; ++i) {
        result -= recur(arr, len, i, 1, bound);
    }
    return result;
}

call it with

unsigned S[N] = {...};
inex(S, N, L-1);

You need not add the 1 for the 0 anywhere, since 0 is divisible by all numbers, compute the count of numbers 1 <= k < L which are not divisible by any s_i.

Question 3

Create an array of flags with L entries. Then mark each touched leaf:

for(each size in list of sizes) {
    length = 0;
    while(length < L) {
        array[length] = TOUCHED;
        length += size;
    }
}

Then find the untouched leaves:

for(length = 0; length < L; length++) {
    if(array[length] != TOUCHED) { /* Untouched leaf! */ }
}

Note that there is no multiplication and no division involved; but you will need up to about 1 GiB of RAM. If RAM is a problem the you can use an array of bits (max. 120 MiB).

This is only a beginning though, as there are repeating patterns that can be copied instead of generated. The first pattern is from 0 to S1*S2, the next is from 0 to S1*S2*S3, the next is from 0 to S1*S2*S3*S4, etc.

Basically, you can set all values touched by S1 and then S2 from 0 to S1*S2; then copy the pattern from 0 to S1*S2 until you get to S1*S2*S3 and set all the S3's between S3 and S1*S2*S3; then copy that pattern until you get to S1*S2*S3*S4 and set all the S4's between S4 and S1*S2*S3*S4 and so on.

Next; if S1*S2*...Sn is smaller than L, you know the pattern will repeat and can generate the results for lengths from S1*S2*...Sn to L from the pattern. In this case the size of the array only needs to be S1*S2*...Sn and doesn't need to be L.

Finally, if S1*S2*...Sn is larger than L; then you could generate the pattern for S1*S2*...(Sn-1) and use that pattern to create the results from S1*S2*...(Sn-1) to S1*S2*...Sn. In this case if S1*S2*...(Sn-1) is smaller than L then the array doesn't need to be as large as L.

Question 4

I'm afraid your problem understanding is maybe not correct.

You have L. You have a set S of K elements. You must count the sum of quotient of L / Si. For L = 20, K = 1, S = { 5 }, the answer is simply 16 (20 - 20 / 5). But K > 1, so you must consider the common multiples also.

Why loop through a list of subsets? It doesn't involve subset calculation, only division and multiple.

You have K distinct integers. Each number could be a prime number. You must consider common multiples. That's all.

EDIT

L = 20 and S = {3,2,5}

Leaves could be eaten by 3 = 6
Leaves could be eaten by 2 = 10
Leaves could be eaten by 5 = 4

Common multiples of S, less than L, not in S = 6, 10, 15

Actually eaten leaves = 20/3 + 20/2 + 20/5 - 20/6 - 20/10 - 20/15 = 6

Question 5

You can keep track of the distance until then next touched leaf for each size. The distance to the next touched leaf will be whichever distance happens to be smallest, and you'd subtract this distance from all the others (and wrap whenever the distance is zero).

For example:

 int sizes[4] = {2, 5, 7, 9};
 int distances[4];
 int currentLength = 0;

 for(size = 0 to 3) {
     distances[size] = sizes[size];
 }

 while(currentLength < L) {
     smallest = INT_MAX;
     for(size = 0 to 3) {
         if(distances[size] < smallest) smallest = distances[size];
     }
     for(size = 0 to 3) {
         distances[size] -= smallest;
         if(distances[size] == 0) distances[size] = sizes[size];
     }
     while( (smallest > 1) && (currentLength < L) ) {
         currentLength++;
         printf("%d\n", currentLength;
         smallest--;
     }
 }

Question 6

@A.06: u r the one with username linkinmew on opc, rite?

Anyways, the answer just requires u to make all possible subsets, and then apply inclusion exclusion principle. This will fall well within the time bounds for the data given. For making all possible subsets, u can easily define a recursive function.

Question 7

i don't know about programming but in math there is a single theorem which works on a set that has GCD 1 L=20, S=(3,2,5) (1-1/p)(1-1/q)(1-1/r).....and so on (1-1/3)(1-1/2)(1-1/5)=(2/3)(1/2)(4/5)=4/15 4/15 means there are 4 numbers in each set of 15 number which are not divisible by any number rest of it can be count manually eg. 16, 17, 18, 19, 20 (only 17 and 19 means there are only 2 numbers thatr can't be divided by any S) 4+2=6 6/20 means there are only 6 numbers in first 20 numbers that can't be divided by any s