Problema numere mari

[•Mitza444]

Am urmatoarea problema:
Se considera doua numere intregi m si n.Sa se determine cea mai mare valoare k , astfel incat numarul m! sa fie multiplu al numarului n^k(n la puterea k).
Date de intrare
Fisierul de intrare EXPONENT.IN contine o singura linie pe care se afla doua numere intregi,separate printr-un spatiu,reprezentand m si n.
Date de iesire
Fisierul EXPONENT.OUT va contine o singura linie pe care se va afla valoarea k.
Restrictie
2<=m,n<=2000000000(doua miliarde)
Exemplu
EXPONENT.IN                                   EXPONENT.OUT
20 24                                              6
Timpul de executie:1 secunda/test

Eu m-am gandit ca rezolvarea ar trebui implementata pe numere mari deoarece numerele depasesc si long long.Dar daca fac o implementare pe numere mari si il retin pe m! intr-un vector ,iar n^k in altul, ca sa verific daca m! este multiplu pt. n^k ar trebui sa fac impartirea pe numere mari,ceea ce e cam complicat(problema s-a dat la locala).
Ar fi o alta varianta mai usoara??

[•SpiderMan]

Clar ca nu se face cu numere mari, faci asa : prima data iei numarul N si il faci in factori primi, si o sa ai niste exponenti si niste factori primi. Apoi pentru fiecare element al produsului 1 * 2 * ... * M il desfaci in factori primi si numeri de cate ori apare fiecare exponent prim gasit mai sus (adica tu o sa ai pentru N = p1^e1 * p2^e2 * ... * px^ex, si pentru fiecare p1, p2 ... px faci asta). Dupa asta, o sa gasesti alti exponenti, adica f1, f2 ... fx (tot pentru aceiasi factori primi, p1, p2 ..... px). O sa calculezi [f1 / e1], [f2 / e2] .... si iei minimul valorilor. Pentru exemplu asta, o sa ai pe N = 2^3 * 3^1. Acuma, M! = 1 * 2 * .... * 20. Pentru fiecare element din acest produs, tu il descompui, si iei doar EXPONENTII factorilor primi care i-ai aflat adineauri, adica 2 si 3. Sper exemplu, 15 = 2^1 * 5^1. Pe tine te intereseaza doar 2^1 de aici, deci adaugi la f1 valoarea 1 (pentru ca 1 este exponentul lui 2 din descompunerea lui 15). Faci asa pentru fiecare numar, si o sa vezi ca pentru 2, f1 o sa fie 18 (adica dupa ce ai descompus fiecare numar din acelea 20, adunand exponentii lui 2 o sa ai 18, spre exemplu 2 = 2^1, f1 = 1, 4 = 2^2, f1 += 2 = 3, 6 = 2^1 * 3^1, f1 += 1 = 4). Vezi ca pentru f3, exponentul o sa fie 8, si deci valoarea minima dintre [f1 / e1] = [18 / 3] = 6 si [8 / 1] = 8 este 6, acesta este rezultatul corect. Scuze si eu pentru greseala, am corectat-o acuma .

[•fulgerulnegru]

Mai degraba folosesti formula din matematica care iti spune precis
[n/s]+[n/(s*s)]+[n/(s*s*s] + ... pana cand m^t>n si suma aceasta iti da acel k
m o sa il descompun in numere prime intre ele si sa iau cel mai mare numar prim exemplu este 20 ( care il voi scrie 4  * 5 ) deci s = 5 si va da rezultatul pentru n = 24 raspunsul este 4 , daca era n = 25 atunci iesirea era 6

Explicarea formulei cu mentiune ca m trebuie sa fie prim (mersi de observatia ta, nu am fost atent cand am postat pe forum ) indica puterea la care se gaseste m in n !

Scuze pentru greseala