设 $n={{2}^{31}}{{3}^{19}}$，那么 ${{n}^{2}}$ 的小于 $n$ 但不整除 $n$ 为正整数因数有多少？
【难度】
【出处】
1995年第13届美国数学邀请赛（AIME）
【标注】
【答案】
589
【解析】
设 $n={{p}^{r}}{{q}^{s}}$，其中 $p$，$q$ 是不同的素数，那么 ${{n}^{2}}={{p}^{2r}}{{q}^{2s}}$，${{n}^{2}}$ 有 $\left( 2r+1\right)\cdot \left( 2s+1 \right)$ 个因数．对每一个小于 $n$ 的因数，一定有一个对应的大于 $n$ 的因数，另外包含因数 $n$，所以 ${{n}^{2}}$ 的因数中一定有 $\frac{\left( 2r+1 \right)\left( 2s+1 \right)-1}{2}=2rs+r+s$ 个小于 $n$．因为 $n$ 有 $\left( r+1\right)\left( s+1 \right)$ 个因数（包括 $n$ 本身），并且 $n$ 的每一个因数也是 ${{n}^{2}}$ 的因数，所以 ${{n}^{2}}$ 的小于 $n$ 但不整除 $n$ 的正因数有 $2rs+r+s-\left[ \left( r+1 \right)\left( s+1 \right)-1 \right]=rs$ 个．当 $r=31$，$s=19$ 时，有 $rs=589$ 个这样的正因数．
答案
解析
备注
