Mnoge petlje u zadacima samo sabiraju ili broje. Za takve petlje često postoji gotova formula koja daje rezultat odmah, i za brojeve veće od milijardu. Ova lekcija sakuplja najkorisnije formule, sa programima i proverom na primerima.
| Zbir | Formula | Primer |
|---|---|---|
| 1 + 2 + … + n | n(n + 1) / 2 | n = 100 → 5050 |
| 1² + 2² + … + n² | n(n + 1)(2n + 1) / 6 | n = 3 → 14 |
| 1³ + 2³ + … + n³ | (n(n + 1) / 2)² | n = 3 → 36 |
| a + (a+d) + … (n članova) | n · (2a + (n − 1)d) / 2 | aritmetički niz |
| 1 + q + q² + … + qn−1 | (qⁿ − 1) / (q − 1) | q = 2: 2ⁿ − 1 |
| a + (a+1) + … + b | (a + b)(b − a + 1) / 2 | 3 + … + 7 = 25 |
n * (n + 1) / 2 prvo se množi pa deli – proizvod je uvek paran pa je deljenje tačno. Za n do 109 proizvod je do 1018, pa mora long long. Za n do 2·109 i više – podeli parni činilac pre množenja.Od 1 do n ima tačno n / k (celobrojno deljenje) brojeva deljivih sa k. U intervalu [a, b] ih ima b / k − (a − 1) / k (za pozitivne a i b). Njihov zbir je k · (1 + 2 + … + m) = k · m(m + 1) / 2, gde je m = n / k.
Za brojeve deljive sa 3 ili 5 koristi se uključenje–isključenje: deljivi sa 3 + deljivi sa 5 − deljivi sa 15 (oni su ubrojani dva puta).
#include <iostream>
using namespace std;
// zbir svih brojeva od 1 do n deljivih sa k
long long zbirDeljivih(long long n, long long k) {
long long m = n / k; // toliko ih ima: k, 2k, ..., mk
return k * (m * (m + 1) / 2);
}
int main() {
long long n;
cin >> n;
// deljivi sa 3 ili 5 = sa 3 + sa 5 - sa 15
cout << zbirDeljivih(n, 3) + zbirDeljivih(n, 5) - zbirDeljivih(n, 15) << endl;
return 0;
}
Za n = 10: 3 + 5 + 6 + 9 + 10 = 33. Petlja do 109 bi trajala sekundu, a formula je trenutna i radi i za 1012 (uz pažnju na prekoračenje).
| Pitanje | Formula | Zašto |
|---|---|---|
| koliko rukovanja ima n ljudi (svako sa svakim) | n(n − 1) / 2 | parovi bez redosleda |
| koliko uređenih parova različitih elemenata | n(n − 1) | prvi pa drugi |
| koliko podnizova (uzastopnih delova) ima niz dužine n | n(n + 1) / 2 | biraju se početak i kraj |
| koliko kvadrata (svih veličina) ima tabla n × n | 1² + 2² + … + n² | kvadrata veličine k ima (n − k + 1)² |
| koliko pravougaonika ima tabla n × m | C(n+1, 2) · C(m+1, 2) | biraju se dve horizontalne i dve vertikalne linije |
| koliko podskupova ima skup od n elemenata | 2ⁿ | svaki element je unutra ili nije |
Više o ovome je u lekciji Kombinatorika.
Česta ideja: umesto da se broje parovi direktno, prebroje se elementi po grupama, pa se za svaku grupu primeni formula. Primer: koliko ima parova pozicija i < j sa a[i] = a[j]? Ako se vrednost v javlja c puta, ona daje c(c − 1)/2 parova:
#include <iostream>
#include <map>
using namespace std;
int main() {
int n;
cin >> n;
map<long long, long long> br; // koliko puta se javlja svaka vrednost
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
br[x]++;
}
long long parova = 0;
for (auto &p : br) parova += p.second * (p.second - 1) / 2;
cout << parova << endl;
return 0;
}
Umesto O(n²) poređenja svih parova – O(n log n). Ovo je ista ideja kao u zadatku sa binarnim stringom u lekciji Zamena iteracija formulom.
Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.
Koliko ima kvadrata svih veličina na tabli n × n (1 ≤ n ≤ 106)? Na šahovskoj tabli (n = 8) ih ima 204.
112582041000000333333833333500000Dati su brojevi a, b i k (1 ≤ a ≤ b ≤ 1018, 1 ≤ k ≤ 1018). Koliko brojeva iz [a, b] je deljivo sa k?
1 10 3310 20 537 7 20Na turniru igra n ekipa (n ≤ 109) i svaka igra sa svakom po dva puta (domaćin i gost). Koliko ima utakmica?
4121000000000999999999000000000long long u svim međurezultatima.1. Koliko je 1 + 2 + … + 200?
2. Koliko brojeva od 1 do 100 je deljivo sa 7?
3. Koliko uzastopnih delova ima niz od 5 elemenata?