Broj delilaca proizvoda - Rešenje

Razlaganje svakog broja pojedinačno na proste činioce

Broj delilaca se može izračunati, korišćenjem multiplikativnosti funkcije \(\sigma_0\), koja izračunava broj delilaca datog broja. Za ovo je potrebno da se proizvod svih brojeva rastavi na proste činioce. Dovoljno je odrediti eksponent svakog prostog činioca u tom razlaganju. Svaki broj možemo nezavisno razložiti na proste činoice. Možemo održavati niz eksponenata svih potencijalnih činilaca proizvoda (oni su svi manji ili jednaki od najvećeg broja u nizu) i čim element niza razložimo na proste činioce, možemo ažurirati niz eksponenata prostih činilaca proizvoda.

Složenost rastavljanja svakog broja \(N\) na proste činioce vrši se u složenosti \(O(\sqrt{N})\). Neka je \(M\) gornje ograničenje vrednosti elemenata niza. Najgori slučaj nastupa kada su svi elementi niza veliki prosti brojevi (oni mogu biti i jednaki) ili kvadrati prostih brojeva, bliski vrednosti \(M\). Složenost rastavljanja svih brojeva na proste činioce je \(O(n\sqrt{M})\). Broj činilaca nije veći od \(\log{M}\), a možemo ga i smatrati konstantnim (svaki broj koji staje u opseg tipa int ima najviše tridesetak prostih činilaca). Izračunavanje krajnjeg proizvoda izvršava se u složenosti \(O(M)\) (što se može smanjiti na broj različitih prostih činilaca koji se javljaju u proizvodu, ako se umesto niza upotrebi mapa).

Eratostenovo sito

Ako je broj elemenata veliki, tada se umesto nezavisnog rastavljanja svakog broja na proste činioce više isplati primena modifikacije Eratostenovog sita.

Neka je \(M\) maksimalan broj u nizu. Da bismo mogli brzo da faktorišemo veliki broj brojeva iz intervala \([1, M]\), dovoljno je da za svaki broj iz tog intervala odredimo najmanji prost činilac, što se efikasno može uraditi modifikacijom Eratostenovog sita. Nakon toga možemo rastavljati na činioce jedan po jedan element niza, čuvajući globalni niz u kom ćemo pamtiti eksponente svih prostih činilaca proizvoda. Taj niz jednoznačno određuje faktorizaciju proizvoda svih brojeva.

Kada je faktorizacija proizvoda poznata, broj delilaca se određuje korišćenjem svojstva multiplikativnosti funkcije \(\sigma_0\) koja izračunava broj delilaca.

Ako se u nizu brojevi često ponavljaju, da ih ne bismo iznova rastavljali na činioce, možemo prebrojati pojavljivanja svakog elementa u nizu, pa prilikom njegove faktorizacije (koju ćemo vršiti samo jednom), tj. deljenja sa nekim prostim činiocem \(p_i\) eksponent tog prostog činioca uvećavati za broj pojavljivanja tog elementa (a ne za 1).

Za svaki element iz intervala \([1, M]\) najmanji prost činilac se određuje modifikacijom Eratostenovog sita u složenosti \(O(M\log\log M)\). Nakon toga se faktorizacija svakog broja vrši u složenosti \(O(\log{M})\) (jer svaki broj iz intervala \([1, M]\) može imati najviše \(\log{M}\) prostih činilaca). Ukupna složenost je zato \(O(M\log\log{M} + n\log M)\).

// broj delilaca proizvoda elemenata niza a
long long brojDelilacaProizvoda(const vector<int>& a) {
  // najveci element u nizu a
  int max = *max_element(begin(a), end(a));

  // za svaki broj od 1 do max odredjujemo najmanji prost cinilac
  vector<int> najmanjiCinilac(max+1);
  for (int i = 1; i <= max; i++)
    najmanjiCinilac[i] = i;
  for (int i = 2; i * i <= max; i++)
    if (najmanjiCinilac[i] == i)
      for (int j = i*i; j <= max; j += i)
        najmanjiCinilac[j] = i;

  // za svaki prosti cinilac proizvoda pamtimo eksponent u sklopu
  // jedinstvenog razlaganja proizvoda na proste cinioce - cinilac se
  // preslikava u eksponent
  vector<int> eksponentiProstihCinilaca(max+1, 0);

  // rastavljamo svaki broj na proste cinioce
  for (int x : a) {
    while (x != 1) {
      eksponentiProstihCinilaca[najmanjiCinilac[x]]++;
      x /= najmanjiCinilac[x];
    }
  }

  // izracunavamo broj delilaca proizvoda koriscenjem multiplikativnosti
  // funkcije broja delilaca
  long long broj = 1;
  for (int e : eksponentiProstihCinilaca)
    broj = (broj * (e + 1)) % MOD;
  
  return broj;
}

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

using namespace std;

const int MOD = 1e9 + 7;

// broj delilaca proizvoda elemenata niza a
long long brojDelilacaProizvoda(const vector<int>& a) {
  // najveci element u nizu a
  int max = *max_element(begin(a), end(a));

  // za svaki broj od 1 do max odredjujemo najmanji prost cinilac
  vector<int> najmanjiCinilac(max+1);
  for (int i = 1; i <= max; i++)
    najmanjiCinilac[i] = i;
  for (int i = 2; i * i <= max; i++)
    if (najmanjiCinilac[i] == i)
      for (int j = i*i; j <= max; j += i)
        najmanjiCinilac[j] = i;

  // za svaki prosti cinilac proizvoda pamtimo eksponent u sklopu
  // jedinstvenog razlaganja proizvoda na proste cinioce - cinilac se
  // preslikava u eksponent
  vector<int> eksponentiProstihCinilaca(max+1, 0);

  // rastavljamo svaki broj na proste cinioce
  for (int x : a) {
    while (x != 1) {
      eksponentiProstihCinilaca[najmanjiCinilac[x]]++;
      x /= najmanjiCinilac[x];
    }
  }

  // izracunavamo broj delilaca proizvoda koriscenjem multiplikativnosti
  // funkcije broja delilaca
  long long broj = 1;
  for (int e : eksponentiProstihCinilaca)
    broj = (broj * (e + 1)) % MOD;
  
  return broj;
}

int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  cout << brojDelilacaProizvoda(a) << endl;
  return 0;
}