我正在尝试解决一个在线评判问题: 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}，则在0到19之间有6个数字不被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)函数在数组A中生成大小为n的下一个子集，如果没有子集，则返回0，否则返回1。它基于this stackoverflow问题中接受答案描述的算法。
lcm(a,b)函数返回a和b的最小公倍数。 get_lcm(n)函数返回A中所有元素的最小公倍数。它使用属性：LCM(a,b,c) = LCM(LCM(a,b),c)
当我将问题提交给评判机时，它会出现“超时”的情况。如果我们使用暴力解决方法，只能得到50％的分数。由于可能有多达2^20个子集，因此我的算法可能很慢，因此我需要更好的算法来解决这个问题。 编辑：
在编辑代码并将函数更改为欧几里得算法后，我得到了一个错误的答案，但我的代码在时间限制内运行。它给出了一个正确的示例测试答案，但对于任何其他测试用例都不正确；这是我在ideone上运行我的代码的链接，第一个输出是正确的，但第二个不正确。
我的解决问题的方法正确吗？如果是的话，那么我在代码中犯了一个错误，我会找到它；否则，有人可以解释一下问题在哪里吗？