Question

Pentru a evita interceptarea convorbirilor efectuate in timpul unor misiuni importnate, politistii din NYPD s-au hotarat sa schimbe foarte des frecventa radio folosita pentru a comunica intre ei sau cu dispeceratul. Pentru a transmite insa rapid si in siguranta noua frecventa radio ce va fi utilizata, aceasta trebuie sa fie in prealabil codificata. Stiind ca infractorii nu se pricep nici la matematica si nici la informatica, politistii s-au gandit sa transmita un numar natural nenul n, iar noua frecventa sa fie data de produsul p al cifrelor lui n. Singura problema care mai trebuie sa fie rezolvata este aceea a gasirii rapide a numarului natural n, care, in plus, trebuie sa fie si cel mai mic posibil dintre toate numerele naturale nenule care au produsul cifrelor egal cu p.

Cerinta

Fiind dat un numar natural p, sa se determine cel mai mic numar natural nenul n care sa aiba produsul cifrelor egal cu p.

Date de intrare

Fisierul de intrare policefm.in contine pe prima linie numarul p.

Date de iesire

Fisierul de iesire policefm.out va contine pe prima linie numarul cerut n sau 0 daca nu exista nici un numar natural nenul n cu proprietatea ceruta.

Restrictii

0 <= p < 1019
Pentru datele de test, valorile numarului p sunt alese astfel incat 0 < n < 1019

Exemple
policefm.in: 81
policefm.out: 99
policefm.in: 101
policefm.out: 0
policefm.in: 480
policefm.out: 2568

Answer 1

#include <fstream>
using namespace std;

ifstream fin("policefm.in");
ofstream fout("policefm.out");

int main()
{
int p, n = 0, k = 9, putere = 1;

cin>>p;
if(p == 1) n = 1;
while(p > 1 && k > 1)
{
   while(p % k == 0)
   {
      n += putere * k;
      putere *= 10;
      p /= k;
   }
   --k;
}
fout<<n;
}