自动搬运

查看原文

来自洛谷，原作者为

	oscar **

搬运于2025-08-24 21:54:07，当前版本为作者最后更新于2017-09-09 12:59:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

解法0：

学习⑨，输出1

期望得分：0分

解法0.5：

找规律，发现mod10余2的项数上最高位为4，于是直接数学方法算

##很抱歉这个规律是错误的

期望得分0分

解法1：

暴力拿高精度乘，暴力取最高位

时间复杂度O(n^2)

期望得分0分

解法1.5：

对解法1进行有理有据的优化

时间复杂度O(n)

期望得分30~40分

解法1.75：

分段打表

期望得分30~40分

Hint：

找到规律？3/10？301/1000？或者某些奇怪的分数？

有没有想到这些分数在趋近某个无理数

解法2：

观察下图

1--2--4--8

\ \ \

\ 5 9

3--6
7 发现每次乘二后最高位会向右或右下移一格（1->2,1->3,2->4,2->5,...），若到最右侧则一定回到1

又发现所有经过4次回到1的路线都经历了最高位为4的阶段，所有经过3次回到1的路线都没有经过最高位为4的阶段

于是只需要求出2^n共有k位后解方程4x+3(k-x)=n即可

可以使用对数来快速算出k（没错刚才的“趋近某个无理数”就是在说log_10{2}）

时间复杂度O(log(n))

期望得分70~80分

解法3：

使用高精度优化一下

高精log2可以打表或者使用泰勒展开计算

注意提供的高精度库中不包含大整数的高精度部分，所以还是需要手打

时间复杂度O(log(n))

本题标程有17k，比赛的时候尝试写满分做法貌似有点作（逃

改编自美国数学国家队口算题（逃

upd：比赛时好像很多人根据概率分布用log(5/4)水到高分QAQ，而我貌似不会卡？

期望得分100分

不给标程啦