每日一题[2391]容斥

已知正整数 $m,n$ 的最大公约数为 $10!$,最小公倍数为 $50!$,则满足要求的 $(m,n)$ 的组数为(       )

A.$2^{5}$

B.$2^{10}$

C.$2^{15}$

D.$2^{20}$

答案    C.

解析    设 $m=10!\cdot x$,$n=10!\cdot y$,其中 $x,y\in\mathbb N^{\ast}$ 且 $x,y$ 互质,则根据题意,有\[mn=\gcd(m,n)\cdot \mathop{\rm lcm}(m,n)\iff xy=11\cdot 12\cdot 13\cdots 50,\]而 $50$ 以内的质数有\[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,\]共 $15$ 个,记为 $p_i$($i=1,2,\cdots,15$),于是\[xy=\prod_{i=1}^{15}p_i^{k_i},\]注意到 $x,y$ 互质,因此符合要求的 $(x,y)$ 共有 $2^{15}$ 组,也即符合要求的 $(m,n)$ 共有 $2^{15}$ 组.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表评论