Zbir NZD svih parova delilaca - Rešenje

Gruba sila

Traženi zbir se može izračunati po definiciji. Prvo pronalazimo sve delioce broja. Činjenica da se delioci javljaju u paru (ako je delilac broj \(d\), delilac je i broj \(\frac{N}{d}\)), dovoljno je ispitivati samo potencijalne delioce koji su manji od \(\sqrt{N}\).

Nakon toga za svaki par delilaca Euklidovim algoritmom izračunavamo NZD i dobijene vrednosti sabiramo.

Određivanje svih delilaca vrši se u složenosti \(O(\sqrt{N})\). Nakon toga se analizira svaki par delilaca. Ako delilaca ima \(D\), parova ima \(O(D^2)\). Imajući u vidu ograničenja data u tekstu zadatka, vrednost \(D\) može da naraste do nekoliko hiljada, pa ovaj kvadratni faktor može značajno da utiče na lošu efikasnost rešenja. Za svaki par se određuje NZD i to u složenosti \(O(\log{N})\), jer je svaki delilac u paru manji ili jednak od \(N\).

Multiplikativnost i rastavljanje na proste činioce

Neka je

\[f(N) = \sum_{i|N}\sum_{j|N} \textrm{NZD}(i, j).\]

Funkcija \(f\) je multiplikativna, što znači da za bilo koja dva uzajamno prosta broja \(p\) i \(q\) važi \(f(p\cdot q) = f(p) \cdot f(q)\). Multiplikativnost omogućava da se do rešenja dođe razlaganjem broja \(N\) na proizvod prostih činilaca. Naime, ako je \(N = p_1^{k_1}\cdot \ldots\cdot p_m^{k_m}\), tada je \(f(N) = f(p_1^{k_1}) \cdot \ldots\cdot f(p_m^{k_m})\).

Vrednost \(f(p^k)\), gde je prost broj se može izračunati relativno jednostavno. Naime, delioci broja \(p^k\) su redom \(p^0\), \(p^1\), \(\ldots\), \(p^k\). NZD dva takva delioca \(p^i\) \(p^j\) jednak je \(p^{\min(i, j)}\). Zato je

\[f(p^k) = \sum_{i=0}^k\sum_{j=0}^k p^{\min(i, j)}.\]

Ova se suma može i dalje uprošćavati, međutim, pošto je \(k\) uvek prilično mali broj može se izračunavati i direktno.

long long zbirNZDDelilacaProstog(long long p, int k) {
  vector<long long> stepeni(k+1);
  stepeni[0] = 1;
  for (int i = 1; i <= k; i++)
    stepeni[i] = stepeni[i-1] * p;
  
  long long zbir = 0;
  for (int i = 0; i <= k; i++)
    for (int j = 0; j <= k; j++)
      zbir += stepeni[min(i, j)];
  return zbir;
}

long long zbirNZDDelilaca(long long n) {
  long long zbir = 1;
  for (int d = 2; d*d <= n; d++) {
    int k = 0;
    while (n % d == 0) {
      n /= d;
      k++;
    }
    if (k > 0)
      zbir *= zbirNZDDelilacaProstog(d, k);
  }
  if (n > 1)
    zbir *= zbirNZDDelilacaProstog(n, 1);
  return zbir;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long zbirNZDDelilacaProstog(long long p, int k) {
  vector<long long> stepeni(k+1);
  stepeni[0] = 1;
  for (int i = 1; i <= k; i++)
    stepeni[i] = stepeni[i-1] * p;
  
  long long zbir = 0;
  for (int i = 0; i <= k; i++)
    for (int j = 0; j <= k; j++)
      zbir += stepeni[min(i, j)];
  return zbir;
}

long long zbirNZDDelilaca(long long n) {
  long long zbir = 1;
  for (int d = 2; d*d <= n; d++) {
    int k = 0;
    while (n % d == 0) {
      n /= d;
      k++;
    }
    if (k > 0)
      zbir *= zbirNZDDelilacaProstog(d, k);
  }
  if (n > 1)
    zbir *= zbirNZDDelilacaProstog(n, 1);
  return zbir;
}

int main() {
  long long n;
  cin >> n;
  cout << zbirNZDDelilaca(n) << endl;
  return 0;
}

Dokažimo da je funkcija multiplikativna. Neka su \(p\) i \(q\) uzajamno prosti brojevi.

Izračunavamo

\[f(pq) = \sum_{i|pq}\sum_{j|pq} \textrm{NZD}(i, j)\]

Svaki delilac broja \(pq\) se dobija kao proizvod jednog delioca broja \(p\) i jednog delioca broja \(q\). Zato je

\[f(pq) = \sum_{a_1|p,b_1|q}\sum_{a_2|p,b_2|q} \textrm{NZD}(a_1b_1, a_2b_2)\]

Redosled sumiranja se može promeniti

\[f(pq) = \sum_{a_1,a_2|p}\sum_{b_1,b_2|q} \textrm{NZD}(a_1b_1, a_2b_2)\]

Pošto su brojevi \(p\) i \(q\) uzajamno prosti, uzajamno prosti su i svi parovi brojeva \((a_1, b_1)\), \((a_1, b_2)\), \((a_2, b_1)\) i \((a_2, b_2)\), pa je \(NZD(a_1b_1, a_2b_2) = NZD(a_1,a_2) \cdot NZD(b_1, b_2)\).

Zato je

\[\begin{eqnarray*} f(pq) &=& \sum_{a_1,a_2|p}\sum_{b_1,b_2|q} \left(\textrm{NZD}(a_1, a_2) \cdot \textrm{NZD}(b_1, b_2)\right)\\ &=& \sum_{a_1,a_2|p} \textrm{NZD}(a_1, a_2) \cdot \left(\sum_{b_1,b_2|q} \textrm{NZD}(b_1, b_2)\right)\\ &=& \left(\sum_{a_1,a_2|p} \textrm{NZD}(a_1, a_2)\right)\cdot \left(\sum_{b_1,b_2|q} \textrm{NZD}(b_1, b_2)\right)\\ &=& f(p)\cdot f(q) \end{eqnarray*}\]

Rastavljanje broja \(N\) na proste činioce se vrši u složenosti \(O(\sqrt{N})\). Za svaki prost faktor \(p^k\) zbir NZD-ova se računa u složenosti \(O(k^2)\), što se može smatrati praktično konstantnim, s obzirom na jako male moguće vrednosti \(k\).