Problem G
Miniräknaren
Languages
en
sv
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 |
