Problem C
Miniräknaren
Det går rykten om att skolans miniräknare kan trimmas med en hemlig kod. Du har hört att om du kan få miniräknaren att visa den hemliga kålnami-koden på displayen och sedan trycker på likhetstecknet, så kommer miniräknaren att låsa upp flera stycken hemliga matematikfunktioner.
Din kompis har lyckats lista ut vad kålnami-koden är, men hen berättar för dig att du inte får gå tillväga hur som helst för att skriva in koden i miniräknaren. Från början visar miniräknaren $0$. Sedan får du utföra följande operationer:
-
Multiplicera talet som visas med talet $M$.
-
Addera ett valfritt tal $k$ till talet som visas, där $k$ uppfyller $0 \leq k \leq M-1$.
Som tur är har din kompis även lyckats lista ut vad talet $M$ är. Denna komplicerade process kommer endast fungera om du gör så få operationer som möjligt. Därför vill du nu ta reda på hur många operationer som krävs, givet kålnami-koden och talet $M$.
Indata
Den första raden innehåller heltalet $N$ ($1 \le N \le 10^9$), innehållet av kålnami-koden.
Nästa rad innehåller siffran $M$ ($2 \leq M \leq 9$), som beskrivits ovan.
Utdata
Skriv ut ett heltal: minsta antalet operationer som krävs för att få miniräknaren att visa kålnami-koden $N$.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$20$ |
$M=3, N \leq 10$. |
|
$2$ |
$20$ |
$M=2$ |
|
$3$ |
$20$ |
$N \leq 10^5$ |
|
$4$ |
$40$ |
Inga ytterligare begränsningar. |
Förklaring av exempelfall
I exempelfall 1 är ett sätt att skriva in koden med minsta antalet operationer som följande:
-
$+1$
-
$\times 2$
-
$\times 2$
I exempelfall 2 är en optimal lösning är att utföra följande operationer:
-
$+1$
-
$\times 3$
-
$\times 3$
-
$+2$
-
$\times 3$
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
33 3 |
5 |
