Број дељивих у интервалу - Решење

Линеарна претрага

Могуће је направити решење засновано на претрази грубом силом, које укључује коришћење петљи. То решење је најједноставније за разумевање и имплементацију, међутим може бити неефикасно за велику разлику између бројева \(a\) и \(b\). Потребно је у петљи, редом проћи кроз све бројеве од \(a\) до \(b\), проверити за сваки да ли је дељив бројем \(k\) и за сваки који јесте, увећати бројач пронађених бројева. Дакле, овај алгоритам врши бројање елемената филтриране серије узастопних природних бројева из интервала \([a, b]\), а филтрирање се врши на основу провере дељивости која се своди на поређење остатака при дељењу са нулом.

#include <iostream>

using namespace std;

// broj brojeva u intervalu [a, b] deljivih brojem k
int brojDeljivih(int a, int b, int k) {
  int broj = 0;
  for (int i = a; i <= b; i++)
    if (i % k == 0)
      broj++;
  return broj;
}

int main() {
  int a, b, k;
  cin >> a >> b >> k;
  cout << brojDeljivih(a, b, k) << endl;
  return 0;
}

Израчунавање броја дељивих бројева

Да би број \(x\) био дељив бројем \(k\) потребно је да постоји неко \(n\) тако да је \(x=n\cdot k\). Пошто \(x\) мора бити у интервалу \([a, b]\), мора да важи да је \(a \leq n\cdot k\) и \(n \cdot k \leq b\). Најмање \(n\) које задовољава прву неједначину једнако је \(n_l = \left\lceil{\frac{a}{k}}\right\rceil\), највеће \(n\) које задовољава другу неједначину једнако је \(n_d = \left\lfloor{\frac{b}{k}}\right\rfloor\). Било који број из интервала \([n_l, n_d]\) задовољава обе неједнакости и представља количник неког броја из интервала \([a, b]\) бројем \(k\). Слично, било који број из интервала \([a, b]\) дељив бројем \(k\) даје неки количник из интервала \([n_l, n_d]\). Зато је тражени број бројева из интервала \([a, b]\) који су дељиви бројем \(k\) једнак броју бројева у интервалу \([n_l, n_d]\) а то је \(n_d - n_l + 1\) ако је \(n_d \geq n_l\), тј. \(0\) ако је тај интервал празан тј. ако је \(n_d < n_l\). Бројеви \(n_l\) и \(n_d\) се могу одредити, на пример, гранањем.

#include <iostream>

using namespace std;

// broj brojeva u intervalu [a, b] deljivih brojem k
int brojDeljivih(int a, int b, int k) {
  int l = a % k == 0 ? a/k : a/k + 1; // ceil(a/k)
  int d = b / k;                      // floor(b/k)
  int broj = d >= l ? d-l+1 : 0;
  return broj;
}

int main() {
  int a, b, k;
  cin >> a >> b >> k;
  cout << brojDeljivih(a, b, k) << endl;
  return 0;
}

Задатак може ефикасно да се реши тако што се одреди најмањи број већи или једнак броју \(a\) који је дељив бројем \(k\) и највећи број мањи или једнак броју \(b\) који је дељив бројем \(k\). Њиховим дељењем са \(k\) добијају се бројеви \(n_l\) и \(n_d\) описани у претходном решењу и задатак се даље решава на исти начин.

#include <iostream>

using namespace std;

// broj brojeva u intervalu [a, b] deljivih brojem k
int brojDeljivih(int a, int b, int k) {
  int l = a % k == 0 ? a : (a/k + 1)*k;
  int d = b % k == 0 ? b : (b/k)*k; // moze i samo d = (b/k)*k;
  int broj = d >= l ? (d/k - l/k + 1) : 0;
  return broj;
}

int main() {
  int a, b, k;
  cin >> a >> b >> k;
  cout << brojDeljivih(a, b, k) << endl;
  return 0;
}