Rezolvare completă PbInfo #2342 cadouri2

Cerința

După ce au trecut sărbătorile, ca în fiecare an, Moș Crăciun a început să facă inventarul cadourilor rămase pentru anul următor. El are N cadouri și pe fiecare cadou este scris un număr natural. În fiecare an Moș Crăciun trebuie să noteze într-un carnețel cantitatea de fericire pe care o aduc aceste cadouri copiilor.

Pentru a calcula această valoare, prima dată el trebuie să înmulțească toate numerele înscrise pe cele N cadouri. Astfel el obține un număr foarte mare. Apoi el știe că numărul de divizori al acestui număr este cantitatea de fericire pe care el trebuie să o scrie în carnețel. Ajutați-l pe Moș Crăciun să afle cantitatea de fericire a celor N cadouri. Deoarece acest număr este foarte mare voi trebuie sa aflați doar restul împărțirii la 1.000.000.007.

Date de intrare

Pe prima linie a fișierului de intrare ​cadouri2.in​ se află numărul natural N. Pe următoarea linie se află N numere naturale reprezentând numerele care sunt scrise pe cele N cadouri.

Date de ieșire

In fișierul de ieșire ​cadouri2.out ​trebuie să se afle un singur număr care reprezintă cantitatea de fericire a celor N cadouri modulo 1.000.000.007

Restricții și precizări

  • 1 ≤ N ≤ 1000
  • Numerele înscrise pe cadouri sunt numere naturale cuprinse între 1 și 10​6
  • Pentru teste în valoare de ​40 de puncte​, produsul celor N numere este ≤ 10​​9
  • Pentru alte ​10 puncte​, produsul celor N numere este ≤ 10​​12
  • Pentru alte ​20 de puncte, ​numerele înscrise pe cadouri sunt cuprinse între 1 și 1000

Exemplu 1:

cadouri2.in

3 
2 3 4

cadouri2.out

8

Explicație

Produsul celor trei numere este 24. Divizorii acestui număr sunt: 1, 2, 3, 4, 6, 8, 12, 24. În total 8 divizori.

Exemplu 2:

cadouri2.in

5 
12 24 3 7 15

cadouri2.out

120

Explicație

Produsul celor 5 numere este 90720. Acest număr are 120 de divizori.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema cadouri2:

#include <fstream>
#define Nmax 1001
#define SQR 1001
#define MOD 1000000007
using namespace std;

ifstream f("cadouri2.in");
ofstream g("cadouri2.out");

int n,v[Nmax],p[SQR],nrp,fr[SQR],rez;

int main()
{
    //Ciur pana la sqrt(10^6)
    for (int i=2;i<SQR;i++)
        if (p[i]==0)
        {
            p[++nrp] = i;
            for (int j=i+i;j<SQR;j+=i)
                p[j] = 1;
        }

    f>>n;
    for (int i=1;i<=n;i++)
        f>>v[i];

    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=nrp && v[i]>1;j++)
        {
            while (v[i]%p[j]==0)
            {
                v[i]/=p[j];
                fr[j]++;
            }
        }
    }

    rez = 1;
    for (int i=1;i<=nrp;i++)
        rez = (1LL * rez * (fr[i]+1))%MOD;

    for (int i=1;i<=n;i++)
    {
        if (v[i]!=1)
        {
            int nr = 1;
            for (int j=i+1;j<=n;j++)
            {
                if (v[j]==v[i])
                {
                    nr++;
                    v[j] = 1;
                }
            }
            rez = (1LL * rez * (nr+1))%MOD;
        }
    }

    g<<rez;

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2342 cadouri2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2342 cadouri2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!