题解 P3922 【中学数学题】
解法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分
不给标程啦