Rezolvare completă PbInfo #711 desc

Fie n un număr natural nenul, n > 1. Definim n(p) ca fiind descompunerea lui n în sumă de puteri naturale distincte ale numărului prim p.

Exemple:

  • pentru n=10 toate n(p) descompunerile posibile sunt: 10(2)=21+23 şi 10(3)=30+32
  • pentru n=11 toate n(p) descompunerile posibile sunt: 11(2)=20+21+23 şi 11(11)=111

Cerința

Să se scrie un program care citeşte un număr natural n şi determină toate n(p) descompunerile numărului n.

Date de intrare

Fișierul de intrare desc.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire desc.out va conține pe linii separate toate n(p) descompunerile numărului n. Fiecare linie va conţine în ordine:

  • o valoare naturală p reprezentând numărul prim asociat descompunerii;
  • o valoare naturală k, reprezentând numărul de termeni ai descompunerii;
  • Următoarele k valori, numere naturale, reprezintă exponenţii puterilor din descompunere, scrise în ordine crescătoare.

Restricții și precizări

  • 2 ≤ n ≤ 10 000 000
  • Pentru un număr prim p fixat, există o singură n(p) descompunere a unui număr natural n;
  • Descompunerile vor fi afişate în ordinea crescătoare a valorilor identificate pentru p;
  • Pe fiecare linie a fişierului de ieşire, valorile vor fi despărţite prin câte un spaţiu.

Exemplu

desc.in

10

desc.out

2 2 1 3
3 2 0 2

Explicație

10(2)=21+23; 10(3)=30+32. Prima descompunere s-a făcut după numărul prim p=2 şi conţine 2 termeni cu puterile 1 şi 3. A doua descompunere s-a făcut după numărul prim p=3 şi conţine 2 termeni cu puterile 0 şi 2.


Exemplu

desc.in

11

desc.out

2 3 0 1 3 
11 1 1

Explicație

11(2)=20+21+23; 11(11)=111. Prima descompunere s-a făcut după numărul prim p=2 şi conţine 3 termeni cu puterile 0, 1 şi 3. A doua descompunere s-a făcut după numărul prim p=11 şi conţine un termen cu puterea 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 desc:

// varianta iterativa cu calculare factori crescator numai pana la n/2 plus n-1 si n

#include <stdio.h>
#include <math.h>
#define nmax 10000001

using namespace std;

FILE *f = fopen("desc.in","r");
FILE *g = fopen("desc.out","w");

char v[nmax];
int w[nmax/5],nr=0;

int eprim(int x)
{
int d=0,i;
for(i=2;i*i<=x;i++)
    if (x%i==0) d++;
if (d==0)   return x;
    else    return 0;
}


// Ciurul lui Eratostene
void ciur(int n) 
{
  int i, j;
  for (i = 2; i <= n; ++i) {
    if (v[i] == 0) {
      w[++nr]=i;
      for (j = i + i; j <= n; j += i) {
        v[j] = 1;
      }}}
    
}

    
void solve(int q,int prim)
{
bool ok=true;
int i,k=0,fact,x[25];
x[0]=0;
while (q>1&&ok)
    {
    fact=0;
    while (q%prim==0)
        {fact++;q/=prim;}
    if (k>0&&!fact) ok = false;
    x[k+1]=fact+x[k];   
    k++;q--;
    }

if (ok&&!q)
    {   
    fprintf(g,"%d %d ",prim,k);
    for(i=1;i<=k;i++)
        fprintf(g,"%d ",x[i]);
    fprintf(g,"
");
    }
}

int main()
{
int i,q;
fscanf(f,"%d",&q);
ciur((int)sqrt(q));
if (eprim(q-1)) w[++nr]=q-1;
if (eprim(q)) w[++nr]=q;
for(i=1;i<=nr;i++)
    solve(q,w[i]);


fclose(f);
fclose(g);

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 #711 desc

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