数学和逻辑思维的魅力

原创
2019/09/11 20:37
阅读数 141

 

解法1: 暴力破解, 从1到m 逐个进行判断。 得分70 

时间复杂度 O(m * n )

 

解法2: 暴力破解, 但这个暴力破解比第一个暴力破解要稍微好一点点。得分90分

假设 三个质数 3  ,5 ,7 。 必须先从小到大排序。 

7的倍数 有 m/7 个。

5的倍数 有 m/5 个 , 但是这其中有一些是7的倍数 。

3的倍数有 m/3 个 , 但是这里面有5的倍数和7的倍数 。

O( ( m/3+  m/5 + m/7   ) * n )   当 1 / a0 + 1 / a1 + ... + 1 / an < 1 时, 此算法比较占优势。

 

解法3 : 运用数学知识,容斥原理进行解决。 

 当两个质数时        M / a0 + M / a1 - M / lcm(a0,a1)  

当三个质数时   M / a0 + M / a1 + M / a2 -  M / lcm(a0,a1)   - M / lcm(a0,a2)  - M / lcm(a1,a2) +  M / lcm(a0,a1,a2)  

lcm (a0,a1,a2) = a0 * a1 * a2 可能会越界 。 所以 M / a0 / a1 / a2 .

 

从a0 ,a1 , a2 ... a(n-1)  任取m个数  ax1,ax2 ,... ,axm  . 总共有 (2^N - 1)  种取法。  (-1)^(m+1)  M / lcm(ax1,ax2 ,... ,axm) .

设 i > 0 且 i < 2^N 那么i 代表了一种取法。

将i转化为二进制 。 如果二进制第x位为1 则代表取了ax 。 不太好描述,直接上算法。 

 

 

当然这个算法有一个很大的弊端,多做了许多的除法运算。 

M / a0 / a1 ,   M / a0 / a1 / a2  做了5次除法。 实际上如果能记录下  M / a0 / a1 的值 只需要做3次除法即可 。

改进版的算法 。 这个算法之所以更快是因为sum能记录前面的运算结果。 

 

更快的算法。 

考虑到 M / a0 / a1 / a2 / a3 ... / ax  可能为0的情况,  当sum = 0时应该直接结束递归调用。 并且   17 /  3 / 5 / 7  做了三次除法才得到0, 其实做两次除法即可 17 / 7 / 5 即可得到0 .  因此将 a0,a1, a2 , ... ax 按从大到小排序将会是更好的选择。 从结果来看快了将近20% ,从82毫秒下降到56毫秒。 

 

c++ 的实现更加恐怖 4毫秒。

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部