私はオンライン裁判官の問題を解決しようとしています: http://opc.iarcs.org.in/index.php/problems/LEAFEAT
要するに問題：
整数 L と N 個の整数 s1、s2、s3..sN のセットが与えられた場合、0 から L-1 までの si のいずれでも割り切れない数がいくつあるかを見つけなければなりません。
たとえば、与えられた場合、 L = 203、2、5S = {3,2,5}で割り切れない 0 から 19 までの 6 つの数字があるとします。
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 の次のサブセットを生成します。サブセットがない場合は 0 を返し、それ以外の場合は 1 を返します。これは、このスタックオーバーフローの質問Aで受け入れられた回答で説明されているアルゴリズムに基づいています。
このlcm(a,b)関数は、a と b の lcm を返します。このget_lcm(n)関数は、 内のすべての要素の lcm を返しますA。プロパティを使用します：LCM(a,b,c) = LCM(LCM(a,b),c)
ジャッジに問題を提出すると、「制限時間超過」と表示されます。これをブルート フォースで解決すると、50% のマークしか得られません。
最大 2^20 のサブセットが存在する可能性があるため、私のアルゴリズムは遅くなる可能性があるため、この問題を解決するにはより良いアルゴリズムが必要です。
編集：
コードを編集して関数をユークリッド アルゴリズムに変更した後、間違った答えが得られますが、コードは制限時間内に実行されます。サンプル テストに対する正しい答えが得られますが、他のテスト ケースに対する正しい答えは得られません。コードを実行したideoneへのリンクを次に示します。最初の出力は正しいですが、2 番目の出力は正しくありません。
この問題に対する私のアプローチは正しいですか? もしそうなら、私は自分のコードで間違いを犯しており、それを見つけます。そうでなければ、誰かが何が間違っているのか説明してもらえますか?