Faster algorithm for determining 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

In short:

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

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

L <= 1,000,000,000 and N <= 20.

I used the exclusion-inclusion principle to solve this problem:

 /*Let 'T' be the number of integers that are divisible by any of the 'si 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; } 

next_subset(n) generates the next subset of size n in 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 to this stack question.

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

When I submit a problem to a judge, it gives me an “Exceeded term”. If we resolve this using brute force, we will only get 50% of the marks.

Since there can be up to 2 ^ 20 subsets, my algorithm can be slow, so I need a better algorithm to solve this problem.

EDIT:

After editing my code and changing the function in the Euclidean algorithm, I get the wrong answer, but my code works for a period of time. This gives me the correct answer to the test example, but not to any other test cases; here is a link to ideone where I ran my code, the first output is correct, and the second is not.

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

Answer 1

You can also try changing the 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 differences in speed between them are quite 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 

Answer 2

Typically, the lowest common multiple of the subset k for s_i will exceed L for k much less than 20. Thus, you need to stop earlier.

Maybe just by pasting

 if (temp >= L) { break; } 

after

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

will be sufficient.

In addition, the label, if among s_i there is 1 , all numbers are divided 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 him

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

You do not need to add 1 for 0 anywhere, since 0 is divided by all numbers, calculates the number of numbers 1 <= k < L , which are not divisible by any s_i .

Answer 3

I am afraid that your understanding of the problem may be wrong.

You have L. You have a set S of K elements. You must calculate the amount of private L / Si. For L = 20, K = 1, S = {5}, the answer is simply 16 (20 - 20/5). But K> 1, so you must take into account general multiples.

Why iterate over a list of subsets? It does not include the calculation of a subset, only division and several.

You have K different integers. Each number can be a prime number. You should consider common factors. It's all.

EDIT

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

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

General 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

Answer 4

Create an array of flags with L elements. Then mark each affected sheet:

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

Then find the pristine leaves:

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

Note: there is no multiplication and no division; but you will need up to 1 gigabyte of RAM. If RAM is a problem, you can use an array of bits (maximum 120 MiB).

This is only the beginning, as patterns that can be copied instead of generated ones are repeated. 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 the values ​​affected 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 S3 between S3 and S1 * S2 * S3; then copy this pattern until you get to S1 * S2 * S3 * S4 and set all S4 between S4 and S1 * S2 * S3 * S4, etc.

Further; if S1 * S2 * ... Sn is less than L, you know that the pattern will repeat and can generate results for lengths from S1 * S2 * ... Sn to L from the figure. In this case, the size of the array should be only S1 * S2 * ... Sn and should not be L.

Finally, if S1 * S2 * ... Sn is greater than L; then you can generate a template for S1 * S2 * ... (Sn-1) and use this template to create results from S1 * S2 * ... (Sn-1) to S1 * S2 * ... Sn. In this case, if S1 * S2 * ... (Sn-1) is less than L, then the array should not be as large as L.

Answer 5

You can track the distance until you touch the sheet for each size. The distance to the next affected sheet will depend on which distance is the smallest, and you subtract this distance from all the others (and wrap when 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--; } } 

Answer 6

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

In any case, the answer simply requires u to make all possible subsets and then apply the inclusion exclusion principle. This will decrease significantly within the time slots for the data. To create all possible subsets, u can easily define a recursive function.