Rezolvare completă PbInfo #955 Miny

Fie N un număr natural nenul şi N numere naturale nenule: x1, x2,…, xN.
Fie P produsul acestor N numere, P=x1•x2•...•xN.

Cerinţe

Scrieţi un program care să citească numerele N, x1, x2,…, xN şi apoi să determine:
a) cifra zecilor produsului P;
b) cel mai mic număr natural Y, pentru care există numărul natural K astfel încât YK=P.

Date de intrare

Fișierul de intrare miny.in conţine două linii. Pe prima linie este scris numărul natural N. Pe următoarea linie sunt scrise cele N numere naturale x1, x2,…, xN, separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire miny.out va conține:

  • pe prima linie o cifră reprezentând cifra zecilor produsului P;
  • pe a doua linie numărul natural M de factori primi din descompunerea în factori primi a numărului Y;
  • pe fiecare dintre următoarele M linii (câte o linie pentru fiecare factor prim din descompunere) câte două valori F şi E, separate printr-un singur spaţiu, F reprezentând factorul prim iar E exponentul acestui factor din descompunerea în factori primi a lui Y; scrierea în fişier a acestor factori primi se va face în ordinea crescătoare a valorii lor.

Restricții și precizări

  • 2 ≤ N ≤ 50000
  • 2 ≤ x1, x2,…, xN ≤ 10000
  • pentru rezolvarea corectă a cerinței a) se acordă 20% din punctaj iar pentru rezolvarea corectă a ambelor cerințe se acordă 100% din punctaj.

Exemplu 1

miny.in

6
12 5 60 25 4 36

miny.out

0
3
2 2
3 1
5 1

Explicație

Produsul celor 6 numere este: P=12∙5∙60∙25∙4∙36=12960000.
Cifra zecilor lui P este 0.
Se observă că există 3 valori posibile pentru Y: 12960000, 3600 şi 60 deoarece: 129600001=12960000, 36002=12960000, 604=12960000.
Cea mai mică valoare dintre aceste valori este 60, astfel Y=60=22*3*5.

Exemplu 2

miny.in

3
2 5 7

miny.out

7
3
2 1
5 1
7 1

Explicație

Produsul celor 3 numere este: P=2∙5∙7=70. Cifra zecilor lui P este 7. Există o singură valoare posibilă pentru Y: 70.

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 Miny:

//prof Minca Carmen -CNITV

#include <fstream>
#include <iostream>
using namespace std;
char v[10005];
int fr[10005];
int w[10005];

int cmmdc(int a, int b)
{
    while(a&&b)
    if(a>b)a=a%b;
       else b=b%a;
    return a+b;
}
int main ()
{
    int n, N, i, j,x,d, p=1;
    ifstream f("miny.in");
    ofstream g("miny.out");
    n=10000;
    //determinare numere prime <=10000 - Ciurul lui Eratostene
    v[2]=1;
    for(i=3;i<=n; i+=2)v[i]=1;
    for (i=3; i<=n; i+=2)
    {if (v[i]!=0)
        for (j=2*i; j<=n; j+=i)v[j]=0;
    }
    f>>N;//<=50000

    for(i=1;i<=N;i++)
      {f>>x; fr[x]++;//frecventa de aparitie a fiecarui numar din fisier
       p=(p*x)%100;//cifra zecilor produsului
       }
    for(i=2;i<=n;i++)
     {
         if(fr[i])
          if(v[i])w[i]+=fr[i];//i este numar prim si apare de w[i] ori
          else
          {   x=i;//descompun in factori primi pe i
              for(j=2;j<=n && x>1;j++)
                while(v[j] && (x%j==0)&& x>1)
                   {w[j]+=fr[i];x/=j;} //contorizez in w[j] aparitiile factorului prim j

          }
     }
    int M=0;d=0;
    //calculez cmmdc-ul exponentilor factorilor primi din descompunerea lui Y
    for(i=2;i<=n;i++)
     if(w[i])
     {M++; //numarul factorilor primi din descompunerea lui Y
      d=cmmdc(d, w[i]);}
    g<<p/10<<endl<<M<<endl;
    for(i=2;i<=n;i++)
     if(w[i])
      g<<i<<" "<<w[i]/d<<endl; //factorii primi si exponentii lor
    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 #955 Miny

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #955 Miny 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!