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