che sto cercando di risolvere un problema giudice on-line: http://opc.iarcs.org.in/index.php/problems/LEAFEATpiù veloce algoritmo per trovare quanti numeri non sono divisibili per un determinato insieme di numeri
Il problema in breve:
Se ci viene dato un intero L e un insieme di N interi s1, s2, s3..sN, dobbiamo trovare quanti numeri ci sono da 0 a L-1 che non sono divisibili per nessuno dei 'si'.
Ad esempio, se ci sono dati, L = 20 e S = {3,2,5} poi ci sono 6 numeri da 0 a 19 che non sono divisibili per 3,2 o 5.
L < = 1000000000 e N = 20. <
ho usato il principio di inclusione-esclusione per risolvere questo problema:
/*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
Ecco il mio codice per risolvere questo problema
#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;
}
Il next_subset(n) genera la prossima sottoinsieme di dimensione n della matrice A, se non ci sono sottoinsieme restituisce 0 in caso contrario restituisce 1. Si basa su l'algoritmo descritto dalla risposta accettata in this StackOverflow questione.
La funzione lcm(a,b) restituisce l'lcm di aeb. La funzione get_lcm(n) restituisce l'lcm di tutti gli elementi in A. Utilizza la proprietà: LCM(a,b,c) = LCM(LCM(a,b),c)
Quando invio il problema al giudice, il mio limite di tempo è superato. Se risolviamo questo usando la forza bruta otteniamo solo il 50% dei voti.
Come può esserci fino a 2^20 sottoinsiemi il mio algoritmo potrebbe essere lento, quindi ho bisogno di un algoritmo migliore per risolvere questo problema.
EDIT:
Dopo aver modificato il mio codice e cambiando la funzione per l'algoritmo di Euclide, sto ottenendo una risposta sbagliata, ma il mio codice viene eseguito entro il tempo limite. Mi dà una risposta corretta al test di esempio ma non a nessun altro caso di test; ecco un link a ideone dove ho eseguito il mio codice, il primo output è corretto ma il secondo no.
Il mio approccio a questo problema è corretto? Se è allora ho commesso un errore nel mio codice e lo troverò; altrimenti qualcuno può spiegare cosa c'è che non va?
+1 per aver fornito questo sito con così tanti problemi interessanti. Al lavoro! –
La funzione lcm e gcd dovrebbe richiedere a, b quanto a lungo. – nhahtdh