Se dă un şir de n numere naturale nenule x1, x2, …, xn şi un număr natural m.

Cerința

Să se verifice dacă valoarea expresiei \( \sqrt[m]{ x_1 \cdot x_2 \cdot … \cdot x_n } \) este un număr natural. În caz afirmativ să se afișeze acest număr descompus în factori primi.

Date de intrare

Fișierul de intrare exp.in conține pe prima linie m, pe linia a doua n, iar pe linia a treia numerele x1, x2, …, xn separate între ele prin câte un spațiu.

Date de ieșire

În fișierul de ieșire exp.out se va scrie pe prima linie cifra 0, dacă valoarea expresiei nu este un număr natural, respectiv 1 dacă este un număr natural. Dacă valoarea expresiei este un număr natural pe următoarele linii se vor scrie perechi de forma p e (p este factor prim care apare în descompunere la puterea e>=1). Aceste perechi se vor scrie în ordine crescătoare după primul număr (adică p).

Restricții și precizări

0 < n < 5000
0 < x_i < 30.001, pentru orice i=1..n
m poate fi una din cifrele 2, 3, 4.

Exemplul 1:

exp.in

2
4
32 81 100 19

exp.out

Exemplul 2:

exp.in

2
4
32 81 100 18

exp.out

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

#include <bits/stdc++.h>

using namespace std;

bool a[30000];
int n, m, f[3300], e[3300], k;
int t[30003];

void Ciur()
{
    int i, j;
    for (i = 4; i <= 30000; i += 2)
        a[i] = true;
    for (i = 3; i * i <= 30000; i += 2)
        if (!a[i])
        for (j = i * i; j <= 30000; j = j + 2 * i)
            a[j] = true;
    f[1] = 2;
    k = 1;
    for (i = 3; i <= 30000; i += 2)
        if (!a[i]) f[++k] = i;
}

int CautBin(int x)
{
    int st, dr, mij;
    st = 1; dr = k;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (f[mij] == x) return mij;
        if (f[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }
    return 0;
}

void Descompune(int x, int nrap)
{
    int i;
    i = 1;
    while (x > 1 && f[i]*f[i] <= x)
    {
        while (x % f[i] == 0)
        {
            x /= f[i];
            e[i] += nrap;
        }
        i++;
    }
    if (x > 1)
    {
        i = CautBin(x);
        e[i] += nrap;
    }
}

void Citire()
{
    int i, x;
    ifstream fin("exp.in");
    fin >> m >> n;
    for (i = 1; i <= n; i++)
    {
        fin >> x;
        t[x]++;
    }
    fin.close();
}

void Trick()
{
    int i;
    for (i = 1; i <= 30000; i++)
        if (t[i] > 0) Descompune(i, t[i]);
}

void Afisare()
{
    int i;
    ofstream fout("exp.out");
    for (i = 1; i <= k; i++)
        if (e[i] % m != 0)
        {
            fout << "0\n";
            fout.close();
            return;
        }
        else e[i] /= m;
    fout << "1\n";
    for (i = 1; i <= k; i++)
        if (e[i] > 0)
            fout << f[i] << " " << e[i] << "\n";
    fout.close();
}

int main()
{
    Ciur();
    Citire();
    Trick();
    Afisare();
    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 #2141 exp

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

Rezolvare completă PbInfo #2141 exp