# PBinfo #2863 – pyk – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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 \).

## Cod sursă C++

```cpp
#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;
         }
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2863)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2863/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2863/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)