题解 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分 不给标程啦