Niech S i T będą zbiorami skończonymi.
|S ∪ T| = |S| + |T| - |S ∩ T|
Niech zbiór S = {sp, ..., sk}
Niech Da = { n∊S: n dzieli się przez a}
Niech Db = { n∊S: n dzieli się przez b}
Szukamy liczby elementów w zbiorze Da ∪ Db
Łatwo zauważyć, że |Da| wynosi (sp - sk +1) DIV a
Podobnie |Db| wynosi (sp - sk +1) DIV b
|Da ∩ Db | wynosi (sp - sk +1) DIV a*b
|Da ∪ Db| = |Da | + |Db| - |Da ∩ Db |
To co napisałem powyżej pozwala napisać program którego złożoność wynosi O(1)
#include <iostream>
using namespace std;
int main() {
cout<<"Podaj przedzial: ";
int sp,sk;
cin>>sp>>sk;
cout<<"Podaj dwie liczby: ";
int a,b;
cin>>a>>b;
int podzielne_przez_a=(sk/a)-(sp-1)/a;
int podzielne_przez_b=(sk/b)-(sp-1)/b;
int podzielne_przez_ab=(sk/(a*b))-(sp-1)/(a*b);
int podzielne_przez_obie_lub_jedno=podzielne_przez_a+podzielne_przez_b-podzielne_przez_ab;
cout<<"Ilosc liczb podzielnych przez obie lub jedna z liczb wynosi: "<<podzielne_przez_obie_lub_jedno;
return 0;
}