Posts pythonTip 53 神の安♂排
Post
Cancel

pythonTip 53 神の安♂排

题目描述: 记得有一次全班去唱K, 其中有个活动是情歌对唱. 具体操作流程是这样的:准备好 21 个阄(我们班 15 男 6 女), 其中只有两个是有标记的, 每人随意抓取一个, 最后取到有标记的阄的两个人去点首情歌对唱.旁边一哥们儿幽幽地对我说, 看来搅基真是神的安排啊, 你看我们班的男女人数, 搅基的几率 C(15,2)/C(21,2) 刚好是 1/2.给跪了, 这哥们儿对数字太敏感了, 简直是拉马努金转世啊. 不过我随之想到一个问题: (21, 15) 真的是神的唯一安排吗? 其实不是的,神还有很多类似的安排. 比如 (4, 3), 显然 C(4,2)/C(3,2) 也等于 1/2, 当然还有 (120, 85) 等等等等.神的安排太多太多了, 如果我们定义 (n, m) 是一个安排(其中 1 < m < n), 而如果 C(m,2)/C(n,2) = 1/2, 它就是神的安排.现在的问题是, 给你一个不大于 10^9 的正整数 N, 有多少组神的安排 (n, m) 满足 n <= N 呢?

示例:

输入:N = 1 输出:0

分析:

题目呢,就是这么一个题目,我的第一反应是如何去求解。就是按照正常的思路,去判断一个数是不是可以得到神的安排。 然后再以遍历的方式去求解。 然后我算了一下数据范围,10^9 ,每个数都要遍历一下。时间复杂度初步估计 O(n^2) 也就是 10^18, 这时间没了呀。

然后又想,一个 n 可以得到神之安排,肯定是一个确定的,不管N 怎么变化,它都是固定的,所以我心一横,就把所有的 10^9 以内的 n 全部找到,放到一个列表中,然后再去做操作。

代码:

1
2
3
4
5
6
7
x = [4, 21, 120, 697, 4060, 23661, 137904, 803761, 4684660, 27304197]


for key, value in enumerate(x, 0):
    if N < value:
        print(key)
        break
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 52 因子平方和

pythonTip 54 最长回文子串可不简单

Trending Tags