Rezolvare completă PbInfo #2863 pyk

pyk

Fie k, n și y trei numere naturale. Fie X un șir format din n numere naturale: \( x_1, x_2, x_3, …, x_n \). Fie P produsul numerelor \( y, x_1, x_2, x_3, …, x_n \), adică \( P = y\times x_1\times x_2 \times x_3 \times … \times x_n \). Numărul P este o “k-putere” dacă există un număr natural z astfel încât \( P=z^k \).

Cerințe

Scrieți un program care să citească numerele \( k, n, x_1, x_2, x_3, …, x_n \) și care să determine:

  • 1. cel mai mic și cel mai mare număr din șirul X ce sunt formate doar din cifre identice;
  • 2. descompunerea în factori primi a celui mai mic număr natural y (y ≥ 2) cu proprietatea că numărul \( P = y\times x_1\times x_2 \times x_3 \times … \times x_n \) este o “k-putere”.

Date de intrare

Fișierul de intrare pyk.in conține:

  • pe prima linie, un număr natural C, reprezentând cerința din problemă care trebuie rezolvată (1 sau 2);
  • pe a doua linie, numerele naturale k și n, separate printr-un singur spațiu;
  • pe a treia linie, cele n numere naturale \( x_1, x_2, x_3, …, x_n \), separate prin câte un singur spaţiu.

Date de ieșire

Dacă C=1, atunci prima linie a fişierului de ieşire pyk.out va conține două numere naturale, separate printr-un
singur spațiu, reprezentând răspunsul la cerința 1 a problemei. Dacă nu există astfel de numere, prima linie a
fișierului va conține valoarea 1.

Dacă C=2, atunci fișierul de ieşire pyk.out va conține:

  • pe prima linie, un număr natural m reprezentând numărul de factori primi distincți din descompunerea în
    factori primi a numărului y, determinat la rezolvarea cerinței 2;
  • pe fiecare dintre următoarele m linii (câte o linie pentru fiecare factor prim din descompunerea în factori primi
    a lui y), câte două valori F şi E, separate printr-un singur spaţiu, reprezentând factorul prim F și exponentul
    E al 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 ≤ 50.000
  • 2 ≤ k ≤ 100
  • 2 ≤ \( x_1, x_2, x_3, …, x_n \) ≤ 10.000
  • 2 ≤ y
  • pentru rezolvarea corectă a cerinței 1 se acordă 10 puncte;
  • pentru rezolvarea corectă a cerinței 2 se acordă 90 puncte.

Exemplu

pyk.in

1
2 7
122 1111 5 4 88 123 999

pyk.out

4 1111

Explicație

Cerința este 1, k=2, n=7. Numerele din șirul X formate doar din cifre identice sunt: 1111, 5, 4, 88, 999. Cel mai mic număr dintre acestea este 4, iar cel mai mare este 1111.

pyk.in

2
3 6
12 5 60 125 4 36

pyk.out

3
2 1
3 2
5 1

Explicație

Cerința este 2, k=3, n=6. Produsul celor 6 numere din șir este: 12*5*60*125*4*36=64800000. y=90 este cea mai mică valoare pentru care P = 90 * 64800000 = 18003 devine o “k-putere“. Descompunerea în factori primi a lui y conține m=3 factori
primi: \( 2^1\times 3^2\times 5^1 \).

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

#include <fstream>

using namespace std;
int ciur[10001], pt[10001];
int main()
{
    ifstream f("pyk.in");
    ofstream g("pyk.out");
    int n, k, y, x,s, c,t,i, j, xmin=10000, xmax=-1,p,d,m=0,nr=0,eg=0, mare=0,pmax=0;
    bool ok;
    f>>c;
    if(c==1)
        {f>>k>>n;
         for(i=1;i<=n;i++) {f>>x;
                            y=x;
                            ok=0;
                            while(y>9 && ok==0)
                                if(y%10!=y/10%10) ok=1;
                                            else y=y/10;
                            if (ok==0) {if(x>xmax) xmax=x;
                                        if(x<xmin) xmin=x;
                                       }
                             }
            if(xmax==-1) g<<1;
                    else g<<xmin<<' '<<xmax;
        }

    else {f>>k>>n;
    for(i=2;i<=10000;i++)
        if(ciur[i]==0)
         for(j=2;j*i<=10000;j++) ciur[i*j]=1;
         ciur[1]=1;
    //    for(i=1;i<=10000;i++) if (ciur[i]==0) g<<i<<' ';

            xmax=0;
          for(i=1;i<=n;i++) {f>>x;
                             d=2;
                             p=0;
                             while(x%2==0) {p++; x=x/2;}
                             if(p!=0) {pt[2]=pt[2]+p;
                                       if(d>xmax) xmax=d;}

                             if(x!=1) {d=3;
                                        while(x!=1){p=0;
                                                    while(x%d==0&&x!=1)  {p++;
                                                                          x=x/d;}
                                                    if(p!=0) {pt[d]=pt[d]+p;
                                                              if(d>xmax) xmax=d;}
                                                    if(d*d<=x) d=d+2;
                                                         else d=x;
                                                   }
                                           }
                     //       if(x!=1) pt[x]++;

                             }
           for(i=2;i<=xmax;i++) if (pt[i]!=0)
                                        if(pt[i]%k!=0) m++;


           if (m!=0) {g<<m<<'\n';
                      for(i=2;i<=xmax;i++) if (pt[i]!=0 && pt[i]%k!=0) g<<i<<' '<<k-pt[i]%k<<'\n';}

                else  g<<1<<'\n'<<2<<' '<<k;



         }


}

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 #2863 pyk

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