33OJ
登录 注册

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

[ICPC 2019 Nanchang R] Powers of Two

题目描述

Andrew 注意到 77 和 99 是相当不寻常的数字。有一些小的 22 的幂在十进制下以 11 开头(20=12^0 = 1),以 22 开头(21=22^1 = 2),……,以 66 开头(26=642^6 = 64),还有以 88 开头(23=82^3 = 8)。然而,在十进制下以 77 开头的最小的 22 的幂是巨大的 246=70,368,744,177,6642^{46} = 70,368,744,177,664,而以 99 开头的最小的 22 的幂甚至更大:253=9,007,199,254,740,9922^{53} = 9,007,199,254,740,992。

了解到这一点后,Andrew 想更深入地研究 22 的幂。具体来说,他将给出一个数字 pp 和一个正整数 kk,并问你:在十进制下以 pp 开头的第 kk 小的 22 的幂是 22 的多少次幂?

请准备好回答这样的询问!注意,可以证明,对于任意给定的前缀,都存在任意多个以该前缀开头的 22 的幂。

输入格式

输入包含一个正整数 pp(最多 3030 位数字,不包含前导零),以及一个正整数 kk(最大为 7000070000)。

输出格式

输出第 kk 小的非负整数 rr,使得 2r2^r 在十进制下以 pp 开头。

123 1
90
123 12345
3510491
1234567890000000000 67891
192992076478480096905880

提示

为解决本题,你可能需要用到以数学常数 ee 为底的 1010 的对数。以下是其十进制表示,小数点后带有 503503 位小数:

:::align{center} :::

翻译由 DeepSeek V4 Pro 完成