回 帖 发 新 帖 刷新版面

主题:[讨论]C组合趣题

大家都知道C组合的公式吧?这里说明一下:例如
 4 8*7*6*5       m n*(n-1)*...*(m+1)
C =------.通俗一点:C=-------------.
 8 4*3*2*1       n m*(m-1)*...*1
现在的问题是:给出n和m,求组合答案里有多少个不同的质因子(不包括1和它本身.
例如,当m=3,n=7时, 3     140的质因子有2和5和7总共3个,
            C =140,
             7
则应输出3.现请你编出程序.
时间限制:1秒以内,包括1秒.
数据范围:n大于等于m,n小于等于50000.
样例输入1:16 8
样例输出1:5
样例输入2:500 250
样例输出2:65
样例输入1:50000 25000
样例输出1:3489

回复列表 (共3个回复)

沙发

“C =------.通俗一点:C=-------------.”
还有
“时间限制:1秒以内,包括1秒.”
这些不懂

板凳

如果不考虑时间代价的话可以采用如下思路:

如果m>=n/2则输出n以内的所有质数数
当m<n/2时依次取出所有质因子
把所有分子和分母的质因子数相加

3 楼

What else???

我来回复

您尚未登录,请登录后再回复。点此登录或注册