Question

令 $n=2^{31}3^{19}$ 。 $n^2$ 的正整数因数中，有多少个小于 $n$ 但不能整除 $n$ ？

Let $n=2^{31}3^{19}.$ How many positive integer divisors of $n^2$ are less than $n$ but do not divide $n?$

答案

答案：589

知识点：因数个数配对与分组质因数分解

难度评级：2270

小提示：

将每个因数 $d$ （它是 $n^2$ 的因数）与 $\frac{n^2}{d}$ 配对

Pair each divisor $d$ of $n^2$ with $\frac{n^2}{d}$

大提示：

在小于 $n$ 的因数中，减去那些已经能整除 $n$ 的因数

Among the divisors below $n$ , subtract those that already divide $n$

解答：

$n^2=2^{62}3^{38}$ 有 $63\cdot39=2457$ 个因数。把 $d$ 与 $\frac{n^2}{d}$ 配对时，只有 $n$ 没有配对，所以有 $\frac{2457-1}{2}=1228$ 个因数小于 $n$ 。数 $n$ 有 $32\cdot20=640$ 个因数，其中 $639$ 个小于 $n$ 。因此所求数量为 $1228-639=589$ 。

The number $n^2=2^{62}3^{38}$ has $63\cdot39=2457$ divisors. Pairing $d$ with $\frac{n^2}{d}$ leaves only $n$ unpaired, so $\frac{2457-1}{2}=1228$ divisors lie below $n.$ The number $n$ has $32\cdot20=640$ divisors, of which $639$ are below $n.$ Therefore the requested count is $1228-639=589.$

1995 AIME 第 6 题

答案：589

难度评级：2270

小提示：

大提示：

解答：

其他年份的第 6 题