Softescu a învăţat azi la şcoală, la ora de informatică algoritmul determinării exponentului unui număr natural prim p în descompunerea în factori primi a lui n!.
Softescu s-a gândit că ar fi interesant dacă ar putea să elaboreze un algoritm care să determine exponentul unui număr natural oarecare, a (a>1) în descompunerea în factori primi a lui n!.

Cerința

Dându-se două numere naturale n şi a, nenule, se cere să se determine exponentul numărului natural a în descompunerea lui n!.

Date de intrare

Fişierul de intrare exponent.in conţine pe prima linie două numere naturale, nenule, n a separate printr-un spațiu.

Date de ieșire

Fişierul de ieşire exponent.out va conţine pe prima linie un număr natural e, reprezentând exponentul numărului natural a în descompunerea în factori primi a lui n! .

Restricții și precizări

2 ≤ n,a ≤ 1000
pentru 30% dintre teste, 2 ≤ n,a ≤ 200
exponentul unui număr natural nenul x, nu neapărat prim, în descompunerea unui număr natural nenul y este cel mai mare număr natural e cu proprietatea că x^e este divizor al lui y.

Exemplu

exponent.in

6 4

exponent.out

Explicație

6!=1*2*3*4*5*6 = 1*3²*4²*5.

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

#include <fstream>
using namespace std;
ifstream fin("exponent.in");
ofstream fout("exponent.out");
int n,a,k,m,ciur[1001],c[1001],p[1001],e[1001],ea[1001],emin;
void ciurul()
{
    int i,j;
    ciur[0]=ciur[1]=1;
    for(i=2;i<=1000;i++)
    {
        if(ciur[i]==0)
           {k++;
            c[k]=i;
            for(j=i*i;j<=a;j=j+i)
                ciur[j]=1;
           }
    }
}
int exp(int p)
{
    int ex=0,f=p;
    do{
        ex=ex+n/f;
        f=f*p;
      }while(n/f!=0);
    return ex;
}
int main()
{int i,ex;
    fin>>n>>a;
    ciurul();
    i=1;
    while(a>1&&i<=k)
    {
        ex=0;
        while(a%c[i]==0)
        {
            ex++;
            a=a/c[i];
        }
        if(ex)
        {
            m++;
            p[m]=c[i];
            ea[m]=ex;
        }
        i++;
    }
    for(i=1;i<=m;i++)
        {
          e[i]=exp(p[i]);
        }
    emin=e[1]/ea[1];
    for(i=2;i<=m;i++)
        if(e[i]/ea[i]<emin)
             emin=e[i]/ea[i];
    fout<<emin<<'\n';
    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 #1474 exponent

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