fbpx

Problema #2737 – NrDivProd – Rezolvari PBInfo

de Mihai-Alexandru

Cerința

Se dau n numere naturale. Să se afișeze numărul de divizori al produsului tuturor celor n numere citite MODULO 1000000007.

Date de intrare

Programul citește din fișierul nrdivprod.in numărul n, iar apoi n numere naturale, separate prin spații.

Date de ieșire

Programul va scrie în fișierul nrdivprod.out numărul de divizori al produsului celor n numere MODULO 1000000007.

Restricții și precizări

  • 1 ≤ n ≤ 1.000.000
  • cele n numere citite vor fi mai mici decât 1.000.000

Exemplu

nrdivprod.in

3
2 3 4

nrdivprod.out

8

Explicație

2*3*4=24, nrdiv(24)=8

#include <bits/stdc++.h>
using namespace std;

ifstream cin("nrdivprod.in");
ofstream cout("nrdivprod.out");

int f[1000001];

void desc(int n)
{
    int d = 2;
    while(n > 1)
    {
        int p = 0;
        while(n % d == 0)
            p++ , n/=d;
        if(p > 0)
            f[d]+=p;
        d++;
        if(d * d > n)
            d=n;
    }
}

int main()
{
    int n;
    cin >> n;
    int x;
    for(int i = 1 ; i <= n ; ++i)
    {
        cin >> x;
        desc(x);
    }
    long long int nrdiv=1;
    for(int i = 1 ; i <= 1000000 ; ++i)
        nrdiv=(nrdiv*(f[i]+1))%1000000007;
    cout << nrdiv;
    return 0;
}
Comentarii

S-ar putea sa iti placa