更快的算法,用于查找一组给定数字不能分割的数量

Question

我正在尝试解决在线判断问题:http://opc.iarcs.org.in/index.php/problems/LEAFEAT

问题简而言之:

如果我们给出一个整数L和一组N个整数s1,s2,s3..sN,我们必须找到从0到L-1的数字,它们不能被任何'si'整除.

例如,如果我们得到, L = 20和S = {3,2,5}然后有6个号码从0到19,其不被整除3,2或5.

L <= 1000000000且N <= 20.

我使用包含 - 排除原则来解决这个问题:

/*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

这是我的代码来解决这个问题

#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)该阵列中产生大小为n的下一个子集A,如果不存在子集返回0,否则返回1.它是基于由所述接受的答案中描述的算法这个计算器问题.

该lcm(a,b)函数返回a和b的lcm.该get_lcm(n)函数返回所有元素的lcm A.它使用的属性:LCM(a,b,c) = LCM(LCM(a,b),c)

当我向法官提交问题时,它给出了"超出时间限制".如果我们使用蛮力来解决这个问题,我们只得到50%的分数.

由于最多可能有2 ^ 20个子集,我的算法可能会很慢,因此我需要一个更好的算法来解决这个问题.

编辑:

编辑我的代码并将函数更改为Euclidean算法后,我得到了错误的答案,但我的代码在时间限制内运行.它给出了我对示例测试的正确答案,但没有给出任何其他测试用例; 这里是我运行代码的ideone的链接,第一个输出正确但第二个输出不正确.

我对这个问题的处理方法是否正确？如果是,那么我在我的代码中犯了一个错误,我会找到它; 否则任何人都可以解释有什么问题？

Answer 1

您还可以尝试更改lcm函数以使用欧几里德算法。

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

至少对于Python来说，两者之间的速度差异相当大：

>>> %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