Mihai a primit în dar un calculator care poate determina numărul de divizori ai unui număr natural. Singura problemă este că afişajul calculatorului îi permite să lucreze numai cu numere formate din cel mult K cifre. Pentru că la şcoală se lucrează cu numere naturale mari, adică numere care au foarte multe cifre, Mihai s-a hotărât ca pentru un număr mare să procedeze astfel: află numărul de divizori al numărului format doar din primele K cifre ale numărului dat. Numărul afişat ca rezultat îl completează alipind la dreapta sa următoarele cifre din numărul iniţial, până ajunge iar la un număr format din K cifre. Acestui nou număr, îi află numărul de divizori şi repetă procedeul până la epuizarea cifrelor numărului iniţial.
Chiar dacă la un moment dat nu mai are cifre pentru a completa numărul afişat ca rezultat, Mihai foloseşte în continuare calculatorul şi determină numărul divizorilor acestuia, continuând până ajunge la un număr care este egal cu numărul divizorilor săi.
Cerinţă
Având dat un număr natural cu N cifre şi un calculator care poate prelucra numere cu cel mult K cifre, Mihai vă roagă să-l ajutaţi acum să afle răspunsuri la următoarele întrebări:
a) pentru câte numere de cel mult K cifre va folosi calculatorul pentru a determina numărul de divizori, urmând exact procedeul descris mai sus?
b) care este valoarea ce reprezintă numărul maxim de divizori obţinută în urma calculelor efectuate de Mihai?
c) care este numărul cu cei mai mulţi divizori din şirul numerelor prelucrate de Mihai? Dacă sunt mai multe numere cu acelaşi număr maxim de divizori, se va alege cel mai mic dintre ele.
Date de intrare
Prima linie a fişierului divizori1.in conţine două numere naturale N şi K separate printr-un singur spaţiu, reprezentând numărul de cifre ale numărului natural iniţial, şi respectiv numărul de cifre ale afişajului calculatorului. Linia a doua a fişierului conţine numărul natural cu N cifre pe care îl va prelucra Mihai urmând exact procedeul descris mai sus.
Date de ieşire
Fişierul de ieşire divizori1.out va conţine trei linii:
− pe prima linie se va scrie un singur număr natural reprezentând numărul de aplicări succesive ale procedeului de aflare a numărului de divizori descris mai sus;
− pe a doua linie sa va scrie un singur număr natural reprezentând numărul maxim de divizori;
− pe a treia linie se va scrie un singur număr natural reprezentând cel mai mic număr ce are proprietatea că numărul său de divizori este egal cu numărul maxim de divizori determinat anterior.
Restricţii
• 2 ≤ K ≤ 9
• 2 ≤ N <900 000
• Pentru 40% din teste, N≤ 50 000 şi K≤ 6
Exemple
divizori1.in
divizori1.out
Explicaţii
43 5
5874392065432987667890567800123450889987543
16
48
12012
Cele 16 numere prelucrate sunt: 58743, 12920, 32654, 83298, 87667, 48905, 46780, 12012, 48345, 16088, 89987, 6543, 6, 4, 3, 2.
Dintre acestea, cei mai mulţi divizori (48) îi are numărul 12012