33OJ
登录 注册

#P17811. [ICPC 2019 Nanchang R] Powers of Two

[ICPC 2019 Nanchang R] Powers of Two

Problem Description

Andrew has noticed that 77 and 99 are quite unusual digits. There are small powers of two that start with 11 in decimal notation (20=12^0 = 1), with 22 (21=22^1 = 2), ..., with 66 (26=642^6 = 64), and with 88 (23=82^3 = 8). However, the smallest power of 22 that starts with 77 in decimal notation is the enormous 246=70,368,744,177,6642^{46} = 70,368,744,177,664, and the smallest power of 22 that starts with 99 is even bigger: 253=9,007,199,254,740,9922^{53} = 9,007,199,254,740,992.

Having learned this, Andrew wants to study the powers of two a bit more. More precisely, he will generate a number pp and present a positive integer kk, and ask you: what is the kk-th smallest power of two that starts with pp in decimal notation?

Prepare for answering such requests! Note that it's possible to prove that there exist arbitrarily many powers of two that start with any given prefix.

Input Format

The input will contain one positive integer pp with at most 3030 digits without leading zeroes, and a positive integer kk up to 7000070000.

Output Format

Output the kk-th smallest non-negative integer rr such that 2r2^r starts with pp in decimal notation.

123 1
90
123 12345
3510491
1234567890000000000 67891
192992076478480096905880

Hint

To solve this problem, you may need the logarithm of 1010 to the base of the mathematical constant ee. Here it is in decimal notation with 503503 decimal places after the decimal point:

:::align{center} :::